给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式：
输入第一行给出一个正整数N（<=1000），随后N行，每行按下列格式给出一个人的房产：
编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
其中 编号 是每个人独有的一个4位数的编号；父 和 母 分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0<=k<=5）是该人的子女的个数；孩子i是其子女的编号。
输出格式：
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
输入样例： 10 6666 5551 5552 1 7777 1 100 1234 5678 9012 1 0002 2 300 8888 -1 -1 0 1 1000 2468 0001 0004 1 2222 1 500 7777 6666 -1 0 2 300 3721 -1 -1 1 2333 2 150 9012 -1 -1 3 1236 1235 1234 1 100 1235 5678 9012 0 1 50 2222 1236 2468 2 6661 6662 1 300 2333 -1 3721 3 6661 6662 6663 1 100 输出样例： 3 8888 1 1.000 1000.000 0001 15 0.600 100.000 5551 4 0.750 100.000 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int father[10000]; int rk[10000]={0}; int ft[10000]={0}; int fm[10000]={0}; int visit[10000]={0}; struct node{ int bianhao; int renkou; double fangtao; double fangmian; }; bool comp(const node &a,const node &b){ if(a.fangmian!=b.fangmian) return a.fangmian>b.fangmian; else return a.bianhao<b.bianhao; } int find(int x){ int y; if(father[x]==x){ return x; } else{ y=find(father[x]);//路径压缩也不一定会把所有节点直接指向根节点 father[x]=y; return y; //return别忘记写，不然只是根节点的下属节点进行压缩，而不是所有节点 } } void join(int x,int y) { int x1,y1; x1=find(x); y1=find(y); if(x1<y1){ father[y1]=x1; } else if(x1>y1){ father[x1]=y1; } } int main() { int n,i,b,f,m,k,j,c,tao,mian,F,cou=0; vector<node> A; node B; for(i=0;i<10000;i++){ father[i]=i; } scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d%d%d",&b,&f,&m,&k); visit[b]=1; if(f!=-1){ join(b,f); visit[f]=1; } if(m!=-1){ join(b,m); visit[m]=1; } for(j=0;j<k;j++){ scanf("%d",&c); join(c,b); visit[c]=1; } scanf("%d%d",&tao,&mian); ft[b]=tao; fm[b]=mian; } for(i=9999;i>=0;i--){ //再一遍遍历的时候处理所有信息 if(visit[i]){ F=find(i); //再压缩一次，这样，就都直接和根节点连接了 //printf("i:%d father:%d\n",i,F); rk[F]++; if(F==i){ cou++; B.bianhao=F; B.renkou=rk[F]; B.fangtao=ft[F]*1.0/rk[F]; B.fangmian=fm[F]*1.0/rk[F]; A.push_back(B); } else{ ft[F]+=ft[i]; fm[F]+=fm[i]; } } } printf("%d\n",cou); sort(A.begin(),A.end(),comp); for(vector<node>::iterator it=A.begin();it!=A.end();it++){ printf("d %d %.3f %.3f\n",(*it).bianhao,(*it).renkou,(*it).fangtao,(*it).fangmian); } }这道题主要考了并查集
主要要注意路径压缩
还有处理整个集合的所有信息
一般得重新再遍历一遍，然后再一遍进行路径压缩
使得每个节点直接和根节点连接
