Codeforces Round #728 (Div. 2) C. Great Graphs

题意

给你一个数组\(d\)，\(d[i]\)表示从节点\(1\)到其他各个节点的最短路的长度，然后你可以对这个图进行加边（可以是负边），但不允许存在一个权值和为负数的回路。

题解

按样例的思想，大概就是将这些点按距离\(1\)的距离从小到大排个序，这样就使得所有点连成一条直线，这样总是可以保证加最多的负边，然后就开始加负边，对于每个点，将他和他前面的点全连上，这样就可以保证加足够多的负边且没有负环。

然后就是计算，很简单的一个推公式，很容易知道，相邻的两个是互相抵消的，不需要计算，设\(S_i\)表示节点\(i\)到节点\(1\)的距离（排序后），则

\[ans=\sum_{i=1}^n\sum_{j=i+2}^n(S_j-S_i)
\]

硬算的话肯定时间超了，于是对\(S_i\)和\(S_j\)分开计算，对于\(S_i\)，它总共被计算了\(n-i-1\)次，最多计算到\(S_{n-2}\)。对于\(S_j\)，它总共被计算了\(j-2\)次，从\(S_3\)开始计算，于是上式又可以写为

\[ans=\sum_{i=1}^{n-2}(n-i-1)(S_{n-i+1}-S_i)
\]

AC代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <iomanip>

#include <cstdio>

#include <vector>

#include <cmath>

#include <stack>

#include <cstring>

#include <map>

#include <set>

#define IO ios::sync_with_stdio(NULL)

#define sc(z) scanf("%d", &(z))

#define _ff(i, a, b) for (ll i = a; i <= b; ++i)

#define _rr(i, a, b) for (ll i = b; i >= a; --i)

#define _f(i, a, b) for (ll i = a; i < b; ++i)

#define _r(i, a, b) for (ll i = b - 1; i >= a; --i)

#define mkp make_pair

#define endl "\n"

#define lowbit(x) x&(-x)

using namespace std;

typedef long long ll;

typedef long double ld;

const int N = 1e5 + 5;

const ll mod = 1e9 + 7;

const ld EPS = 1e-8;

ll d[N];

int main() {

    IO;

    int T; cin >> T;

    while (T--) {

        ll n; cin >> n;

        _ff(i,  1, n) cin >> d[i];

        sort(d + 1, d + 1 + n);

        ll ans = 0;

        _ff(i, 1, n - 2) {

            ans += (n - i - 1) * (d[n - i + 1] - d[i]);

        }

        // ans -= d[n];

        if (ans) cout << "-";

        cout << ans << endl;

    }

    return 0;

}