<span>L2-007 家庭房产 (25分) 并查集</span>
题解：并查集把一个家的并在一起，特殊的一点是编号大的并到小的去。这个题有个坑编号可能为0000，会错数据3和5。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 struct node 5 { 6 int id,num,area,fa,ma; 7 int ch[10]; 8 }p[100100]; 9 10 struct fz 11 { 12 int id,all; 13 double num,area; 14 }q[100100]; 15 16 int par[10100]; 17 int s[10010]; 18 int vis[10010]; 19 20 bool cmp(fz x,fz y) 21 { 22 if(x.area==y.area) return x.id<y.id; 23 return x.area>y.area; 24 } 25 26 void init() 27 { 28 for(int i=0;i<10100;i++) 29 par[i]=i; 30 } 31 32 int find(int x) 33 { 34 if(x!=par[x]) par[x]=find(par[x]); 35 return par[x]; 36 } 37 38 void unionn(int a,int b) 39 { 40 int fa=find(a),fb=find(b); 41 if(fa>fb) par[fa]=fb; 42 else par[fb]=fa; 43 } 44 45 int main() 46 { 47 init(); 48 int n; 49 cin>>n; 50 for(int i=0;i<n;i++){ 51 int k; 52 cin>>p[i].id; 53 s[p[i].id]=1; 54 cin>>p[i].fa>>p[i].ma>>k; 55 if(p[i].fa!=-1){ 56 unionn(p[i].id,p[i].fa); 57 s[p[i].fa]=1; 58 } 59 if(p[i].ma!=-1){ 60 unionn(p[i].id,p[i].ma); 61 s[p[i].ma]=1; 62 } 63 for(int j=0;j<k;j++){ 64 cin>>p[i].ch[j]; 65 if(p[i].ch[j]!=-1){ 66 unionn(p[i].id,p[i].ch[j]); 67 s[p[i].ch[j]]=1; 68 } 69 } 70 cin>>p[i].num>>p[i].area; 71 } 72 for(int i=0;i<10010;i++) 73 q[i].id=-1; 74 int cnt=0; 75 for(int i=0;i<n;i++){ 76 int x=find(p[i].id); 77 if(!vis[x]) cnt++; 78 vis[x]=1; 79 q[x].id=x; 80 q[x].num+=p[i].num; 81 q[x].area+=p[i].area; 82 } 83 for(int i=0;i<10010;i++) 84 if(s[i]) q[find(i)].all++; 85 for(int i=0;i<10010;i++){ 86 if(q[i].id!=-1){ 87 q[i].num=q[i].num/1.0/q[i].all; 88 if(q[i].all) q[i].area=q[i].area/1.0/q[i].all; 89 } 90 } 91 sort(q,q+10010,cmp); 92 printf("%d\n",cnt); 93 for(int i=0;i<cnt;i++){ 94 printf("%04d %d %.3f %.3f\n",q[i].id,q[i].all,q[i].num,q[i].area); 95 } 96 return 0; 97 }
