这题一拿到手当做BFS来做了。做到后面不能得到样例结果，冷静一分析，发现应该用并查集来做。经过这道题。我对并查集的理解更加深入了。
AC代码：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 10010 #define MAX (1<<30)+1 #define V vector<int> using namespace std; int fa[LEN] ; int findFa(int x){ if(fa[x]==x) return x; int r=x; while(fa[r]!=r){ r=fa[r]; } int t=x; while(fa[x]!=x){ t=fa[x]; fa[x]=r; x=t; } return r; } void Union(int a,int b){//让集合b并到集合a上 int f_a=findFa(a); int f_b=findFa(b); fa[f_b]=f_a; } void init(){ int i; FF(i,LEN) fa[i]=i; } int N,M; struct Node{ int id,fa=-1,mo=-1; vector<int> c; int n=0,a=0; //num, area }nd[LEN]; vector<int> inputId; int vis[LEN]; struct oNode{ int id,m; double n,a; }; vector<oNode> output; bool cmp(oNode a,oNode b){ if(a.a!=b.a) return a.a>b.a; return a.id<b.id; } set<int> idSet; int cnt[LEN]; int area[LEN]; int estate[LEN]; int minID[LEN]; int main(){ // freopen("I:\pat\并查集\1114.txt","r",stdin); fill(minID,minID+LEN,MAX); I("%d",&N); int id,t,i,j; init(); while(N--){ I("%d",&id); nd[id].id=id; inputId.push_back(id); I("%d%d",&nd[id].fa,&nd[id].mo); I("%d",&M); while(M--){ I("%d",&t); nd[id].c.push_back(t); } I("%d%d",&nd[id].n,&nd[id].a); } FF(i,inputId.size()){ int id=inputId[i]; int father=nd[id].fa; if(father>=0) Union(id,father); int mother=nd[id].mo; if(mother>=0) Union(id,mother); vector<int>& cv=nd[id].c; FF(j,cv.size()){ int cd=cv[j]; if(cd>=0) Union(id,cd); } } FF(i,inputId.size()){ int id=inputId[i]; int f=findFa(id); idSet.insert(f); //统计人数 if(vis[id]==0){ vis[id]=1; cnt[f]++; minID[f]=min(minID[f],id); } int father=nd[id].fa; if(father>=0 && vis[father]==0){ cnt[f]++; vis[father]=1; minID[f]=min(minID[f],father); } int mother=nd[id].mo; if(mother>=0 && vis[mother]==0){ cnt[f]++; vis[mother]=1; minID[f]=min(minID[f],mother); } vector<int>& cv=nd[id].c; FF(j,cv.size()){ int cd=cv[j]; if(cd>=0 && vis[cd]==0){ Union(f,cd); cnt[f]++; vis[cd]=1; minID[f]=min(minID[f],cd); } } //增加财产 area[f]+=nd[id].a; estate[f]+=nd[id].n; } set<int>::iterator it=idSet.begin(); while(it!=idSet.end()){ int id=*it; oNode tmp; tmp.id=minID[id]; tmp.m=cnt[id]; tmp.a=(double)area[id]/(double)tmp.m; tmp.n=(double)estate[id]/(double)tmp.m; output.push_back(tmp); it++; } sort(output.begin(),output.end(),cmp); O("%d ",output.size()); FF(i,output.size()){ O("%04d %d %.3f %.3f ",output[i].id,output[i].m,output[i].n,output[i].a); } return 0; }