多校联盟-（）

问题链接：https://vjudge.net/contest/152653#problem/E

题意：n个人，m种关系，每个人有一定的金钱，互相认识的可看做一个集群，

问各个集群的总钱数是多少，输出答案非递减

题解：并查集裸题

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<string> #include<map> using namespace std; #define maxn 5005 int a[maxn]; int parent[maxn],ans[maxn]; int find (int x) { if(parent[x]==-1) return x; return parent[x] = find(parent[x]); } int main() { int n,m,T,x,y,i,j,cases=0,k; scanf("%d",&T); while(T--) { k=0; memset(parent,-1,sizeof(parent)); memset(ans,0,sizeof(ans)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); int t1=find(x),t2=find(y); if(t1!=t2) { parent[t1]=t2; } } for(i=1;i<=n;i++) ans[find(i)]+=a[i]; sort(ans+1,ans+n+1); for(i=1;i<=n;i++) if(ans[i]) k++; printf("Case %d: %d\n",++cases,k); for(i=2;i<=n;i++) if(ans[i]) printf("%d ",ans[i]); printf("\n"); } }