思路：先考虑一种普遍解法。
对于每个极大连通块，一次次块上的全部点减去1，断开为子图后继续重复减1，显然是最优的减法。
但是减去后遍历边的复杂度过高，且b值也很大，所以考虑成加边的形式。
首先将点按权值降序。那么我们可以采取将最大的点减成第二大的点，然后两个点又一起减成第三大的点，然后三个点一起减成第四大.....
那么显然这中间能不能一起减去这个代价会是分界，当两个点可以从之前的点间接相连，或者他们可以直接相连时，那么显然可以一起减，
因为之前的点显然和他们已经减到了相同代价。如果不能直接或者间接相连，那么就是两个不同的连通块里的点，那么就要*连通块的个数。
那么每一次的代价就是 num(连通块) * (b[i] - b[i+1]).
所以，我们用并查集来维护连通块的个数，每次计算一个点时，先将这个点合并到和它相连的点且之前出现过的点的连通块中。
Code:
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<int,int> pii; const int N = 1e5+5; const LL Mod = 1e9+9; #define pi acos(-1) #define INF 1e8 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int x = 0,f = 1;char c = getchar(); while(c < ‘0‘ || c > ‘9‘){if(c == ‘-‘) f = -1;c = getchar();} while(c >= ‘0‘ && c <= ‘9‘){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } struct Node{ int val,id; bool operator < (const Node &a)const{ return val > a.val; } }p[N]; int vis[N],fa[N]; vector<int> G[N]; int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); } int main() { freopen("data1.in","r",stdin); freopen("data1.out","w",stdout); int t;t = read(); while(t--) { int n,m; n = read(),m = read(); for(int i = 1;i <= n;++i) { p[i].val = read(); p[i].id = fa[i] = i; G[i].clear(); vis[i] = 0; } sort(p+1,p+n+1); p[n+1].val = 0; while(m--) { int u,v; u = read(),v = read(); G[u].push_back(v); G[v].push_back(u); } LL ans = 0; int cnt = 0;//连通块数量 for(int i = 1;i <= n;++i) { int x = p[i].id; vis[x] = 1; cnt++; for(auto v : G[x]) { if(!vis[v]) continue; int xx = Find(x),yy = Find(v); if(xx != yy) { fa[xx] = yy; cnt--; } } ans += 1LL*(p[i].val-p[i+1].val)*cnt; } printf("%lld\n",ans); } system("pause"); return 0; }
原文：https://www.cnblogs.com/zwjzwj/p/13370013.html
