L2-007. 家庭房产
给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式：
输入第一行给出一个正整数N（<=1000），随后N行，每行按下列格式给出一个人的房产：
编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
其中 编号 是每个人独有的一个4位数的编号；父 和 母 分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0<=k<=5）是该人的子女的个数；孩子i是其子女的编号。
输出格式：
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
做题思路：
1、观察最后两行会发现，2222和2333有相同的孩子——他们的关系没法通过父母的关系网连接到一块；
所以输入孩子也应该连接进关系网中，如果在网中，孩子的父母也指向孩子的根节点；
否则，孩子指向他的该行的父或者母。
2/最后并查集记得进行再次全体进行寻根一次！
3、每次新开一个b【】数组时，记得立即初始化一次！！
4.还出了一个段错误！ 您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起！
后来造了一组无厘头的数据：
3
1222 0 23 0 3 300
0 3 -1 0 1 0
3 0 -1 0 1 0
然后程序就炸了，接着仔细想想——搞了半天我没用上并查集的基本操作add（）！！
AC程序：（附注释）
#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<set> #include<vector> #include<map> #define maxn 400000 #define inf 0x3f3f3f3f using namespace std; #define N 10018 struct node{ int mo,fa; int k;//从0开始的 int kids[7]; int suit; int area; }a[N]; struct family{ int root;//记录根的id int minn_id; int pnum;//人口总数 int suit;double avesuit; int area;double avearea; }b[N]; int tree[N];//建立一棵并查集,tree[i]=x,x表示i的父节点 int vis[N];//记录i是否记录进了人数 int getfa(int x){ if(x==tree[x]) return x; return tree[x]=getfa(tree[x]); } void add(int x,int y){ int fa=getfa(x); int fb=getfa(y); if(fa!=fb){ tree[fa]=fb; } } void init(family &x){ x.area=0;x.suit=0; x.minn_id=19999;x.pnum=0; } int fact1id(int i){ int num=i; if(a[i].mo!=-1) num=min(a[i].mo,num); if(a[i].fa!=-1) num=min(a[i].fa,num); for(int j=1;j<=a[i].k;j++){ num=min(a[i].kids[j],num); } return num; } int fact2(int i){ int num=0; if(vis[i]==0){//别把自己也忘了！ num++;vis[i]=1; } if(a[i].mo!=-1&&vis[a[i].mo]==0){ num++;vis[a[i].mo]=1; } if(a[i].fa!=-1&&vis[a[i].fa]==0){ num++;vis[a[i].fa]=1; } for(int j=1;j<=a[i].k;j++){ if(vis[a[i].kids[j] ]==1)continue; num++; vis[a[i].kids[j] ]=1; } return num; } bool cmp(family x,family y){ if(fabs(x.avearea-y.avearea)<1e-10) return x.minn_id<y.minn_id; return x.avearea>y.avearea; } int main(){ int i,j,n; scanf("%d",&n); memset(vis,0,sizeof(vis)); for(int i=0;i<=10000;i++){ tree[i]=i; a[i].area=-1; } while(n--){ int id; scanf("%d",&id); scanf("%d%d",&a[id].fa,&a[id].mo);//确认并查集树上的父子关系 if(a[id].fa!=-1){ add(id,a[id].fa); } if(a[id].mo!=-1){ add(id,a[id].mo); } getfa(id); scanf("%d",&a[id].k); for(int i=1;i<=a[id].k;i++){//读入他的k个孩子的ID scanf("%d",&a[id].kids[i]); add(id,a[id].kids[i]); } scanf("%d%d",&a[id].suit,&a[id].area); } for(int i=0;i<=9999;i++)//并查集重新调整一次！ getfa(i); int cnt=0;//统计家庭数 set<int>s;//记录根节点 for(int i=0;i<=9999;i++){ if(a[i].area==-1){//不存在 continue; } int fa=tree[i]; int k;//表示开的family数组的序号 if(s.count(fa)>0){ for(int j=1;j<=cnt;j++){ if(b[j].root==fa){ k=j;break; } } }else{ s.insert(fa); ++cnt; k=cnt; b[cnt].root=fa;//需要添加，别忘记了 init(b[k]); } //将a[i]数组的内容转移到b[k]中 b[k].area+=a[i].area; b[k].minn_id=min(b[k].minn_id,fact1id(i) ); b[k].pnum+=fact2(i); b[k].suit+=a[i].suit; } for(int i=1;i<=cnt;i++){ b[i].avearea=b[i].area*1.0/(1.0*b[i].pnum); b[i].avesuit=b[i].suit*1.0/(1.0*b[i].pnum); } sort(b+1,b+1+cnt,cmp); printf("%d ",cnt); for(int i=1;i<=cnt;i++){ printf("%04d %d %.3lf %.3lf ",b[i].minn_id,b[i].pnum,b[i].avesuit,b[i].avearea); } return 0; }