题目大意：有一个n个点m条边的无向图，结点从1开始编号到n，每个结点都有一个权值bi，现在希望可以将所有结点的权值改为0。可以进行下面的操作：选择一个正整数k(1<=k<=n)，选择k个不同的结点c1, c2, ..., ck(1<=ci
官方题解：
每次一定是选择一个极大连通块，将里面所有数同时减小，直到最小值变成 0，然后将变 成 0 的点删除，分裂成多个连通块再接着做。
为了实现这个策略，可以将整个过程倒过来看，变成按照 b 的值从大到小依次加入每个点。 加入每个点 x 时遍历与 x 相连的所有边 (x,y)，如果 y 在 x 之前加入且 x 和 y 不连通则将 x 和 y 合并，并将 y 所在连通块的树根的父亲设为 x，得到一棵有根树。那么每个点 x 在成为最小值之前已经被做了 bfatherx 次操作，所以每个点 x 对答案的贡献为 bx − bfatherx。 使用并查集支持路径压缩，时间复杂度 O((n + m)logn)。
理解：
先是一起对整个极大连通分量中的所有点的权值进行减少，然后有的点权变为0，这个点可看成被删除了，然后这个大的连通分量就变成了许多小的连通分量，然后继续删。
对于一个连通块来说，一定是点按照权值从小到大被删。把操作顺序倒过来，就是把大的结点减小成和小的结点相同，然后一起删掉。
代码如下：
1 #include <bits/stdc++.h> 2 typedef long long LL; 3 #define pb push_back 4 #define mst(a) memset(a,0,sizeof(a)) 5 const int INF = 0x3f3f3f3f;//0x7fffffff; 6 const double eps = 1e-8; 7 const int mod = 1e9+7; 8 const int maxn = 1e5+10; 9 using namespace std; 10 11 struct edge 12 { 13 int to; 14 int next; 15 }E[10*maxn];//注意边的条数,无向图至少要开两倍 16 int head[maxn], tot; 17 void add(int u,int v) 18 { 19 E[tot].to = v; 20 E[tot].next = head[u]; 21 head[u] = tot++; 22 } 23 24 int n,m; 25 int fa[maxn]; 26 int Find(int x) 27 { 28 return x==fa[x]? x : fa[x]=Find(fa[x]); 29 } 30 void Union(int a,int b) 31 { 32 int aa = Find(a); 33 int bb = Find(b); 34 if(aa!=bb) fa[aa] = bb; 35 } 36 37 int pre[maxn];//每个点的父亲节点,即之前的连通分量减到了这个点的权值 38 int rk[maxn];//权值第i大的点的编号 39 int wake[maxn];//标记每个点是否在连通分量中 40 int a[maxn];//点的权值 41 42 init() 43 { 44 tot = 0; 45 for(int i=0;i<=n;i++) 46 { 47 head[i] = -1; 48 pre[i] = wake[i] = 0; 49 rk[i] = fa[i] = i; 50 } 51 } 52 53 bool cmp(int x, int y) 54 { 55 return a[x]>a[y]; 56 } 57 58 int main() 59 { 60 #ifdef DEBUG 61 freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout); 62 #endif 63 64 int T; 65 scanf("%d",&T); 66 while(T--) 67 { 68 scanf("%d %d",&n,&m); 69 init(); 70 for(int i=1;i<=n;i++) 71 scanf("%d",&a[i]); 72 for(int i=1;i<=m;i++) 73 { 74 int u,v; 75 scanf("%d %d",&u,&v); 76 add(u,v); add(v,u); 77 } 78 sort(rk+1,rk+1+n,cmp); 79 for(int i=1;i<=n;i++) 80 { 81 int t = rk[i]; //选择当前权值最大的一个点 82 wake[t] = 1; //将其唤醒 83 for(int j=head[t];j!=-1;j=E[j].next) 84 { 85 int v = E[j].to; 86 if(!wake[v]) continue; 87 int vv = Find(v); 88 if(vv == t) continue; 89 pre[vv] = fa[vv] = t; 90 } 91 } 92 LL ans = 0; 93 for(int i=1;i<=n;i++) 94 ans += a[i]-a[pre[i]]; 95 //因为之前的连通分量所有点的权值全为a[i],他们加上了pre[i]这个点,权值就全变成a[pre[i]]了,故对ans贡献值为a[i]-a[pre[i]] 96 printf("%lld\n",ans); 97 } 98 99 return 0; 100 }
-