【并查集】PAT 家庭房产（25 分）

家庭房产（25 分）"/>

【并查集】PAT 家庭房产（25 分）

Step 1 Problem：

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
给你N行，对于每行给你的详细信息，有自己的编号，父亲编号，母亲编号，孩子的编号，你拥有的房产套数，总面积。其中编号是每个人独有的一个4位数的编号
输出格式：家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积（其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。）

Step 2 Involving algorithms：

并查集，快速排序

Step 3 Ideas：

就是一个数据量很多的模拟，你只需要把属于一个家庭关系的成员用并查集 合并在一起，这样你就可以得到有多少个家庭。
你在遍历每个家庭，求记录该家庭有多少个人，总房产套数，总面积。
然后调用一波快排，输出即可

Step 4 Code：

#include<bits/stdc++.h>
using namespace std;
struct node
{int hnum, area;node(){hnum = area = 0;}
};
struct Ans
{int id, num;double avehnum, avearea;bool operator < (const Ans &b) const {//家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出if(b.num*avearea == num*b.avearea) return id < b.id;else return b.num*avearea > num*b.avearea;}
};
node a[10010];
int f[10010];
Ans ans[10010];
bool vis[10010], vv[10010];
int Find(int x)
{if(x == f[x])return x;else {f[x] = Find(f[x]);return f[x];}
}
void Merge(int x, int y)
{x = Find(x);y = Find(y);if(x != y){f[y] = x;}
}
void init()
{memset(vis, 0, sizeof(vis));memset(vv, 0, sizeof(vv));for(int i = 0; i <= 10000; i++)f[i] = i;
}
int main()
{int n, k, zd, fd, md, cd;scanf("%d", &n);init();for(int i = 0; i < n; i++)//将家庭成员 合并在一起{scanf("%d %d %d", &zd, &fd, &md);vis[zd] = 1;if(fd != -1)Merge(zd, fd), vis[fd] = 1;if(md != -1)Merge(zd, md), vis[md] = 1;scanf("%d", &k);for(int j = 0; j < k; j++){scanf("%d", &cd);Merge(zd, cd), vis[cd] = 1;}scanf("%d %d", &a[zd].hnum, &a[zd].area);}int top = 0;for(int i = 0; i < 10000; i++)//求家庭信息{if(vis[i]) {int x = Find(i);if(vv[x]){for(int j = 0; j < top; j++){if(Find(ans[j].id) == x){ans[j].num++;ans[j].avearea += a[i].area;ans[j].avehnum += a[i].hnum;break;}}}else{vv[x] = 1;ans[top].id = i;ans[top].num = 1;ans[top].avearea = ans[top].avehnum = 0;ans[top].avearea += a[i].area;ans[top++].avehnum += a[i].hnum;}}}sort(ans, ans+top);printf("%d\n", top);for(int i = 0; i < top; i++){printf("%.04d %d %.3lf %.3lf\n", ans[i].id, ans[i].num, 1.0*ans[i].avehnum/ans[i].num, 1.0*ans[i].avearea/ans[i].num);}return 0;
}