SPOJ-IAPCR2F
n个点m条边的无向图，每个点有一个权值，求每个联通块的总权值
dfs 或并查集，统计一下即可
#include <cstdio> #include <queue> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn=1007; int n,m; int head[maxn],to[maxn*maxn],cnt,ne[maxn*maxn]; vector<int> ans; int vis[maxn],a[maxn]; void addedge(int a,int b) { ne[++cnt]=head[a]; head[a]=cnt; to[cnt]=b; } int dfs(int u) { int res=a[u]; for(int i=head[u];i;i=ne[i]) { int v=to[i]; if(vis[v]) continue; vis[v]=1; res+=dfs(v); } return res; } int main() { int T; int kase=0; scanf("%d",&T); while(T--) { ans.clear(); memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); cnt=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int ta,tb; for(int i=1;i<=m;i++) { scanf("%d%d",&ta,&tb); addedge(ta,tb); addedge(tb,ta); } for(int i=1;i<=n;i++) if(!vis[i]) { vis[i]=1; ans.push_back(dfs(i)); } sort(ans.begin(),ans.end()); printf("Case %d: %d\n",++kase,ans.size()); for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i==ans.size()-1?'\n':' '); } return 0; }