[PAT] A1114 Family Property

并查集

题目大意

给出每个人名下的房产和家庭关系，求出每个家庭的总人数即人均房产数和房产面积。第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积。其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出；若有并列，则按成员编号的升序输出。

思路

用并查集。分别用两个结构体存储，一个用来接收输入的数据，一个用于保存答案。（一开始我只用了一个，导致后面自己都乱套了，写不下去。为什么要用两个呢？因为可以注意到输入和结果的域有所不同，输入是按照个人对应名下房产，结果是按照家庭对应任何家庭成员的所有房产，即存在一个合并的关系。如果用一个的话，合并后的结果要与之前的分开，这样非常容易混乱。而如果在合并的时候，将结果做相加等运算迁移到另一个结构体中，思路就很清晰。） 其实输入的数据property可以不用开到10000个，在结构体中加入id即可，这样可以节省空间。（因为property不涉及id之间的关系，父子关系保存在另外的数组中；也不需要排序。它的作用只是别人调用它来获取信息）

AC代码

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include <cstdio> #include <vector> #include<algorithm> using namespace std; #define N 10000 struct root { int id, numpeople; int num, area; }ans[N]; struct own { int id, num, eara; }property[N]; bool exist[N] = { false };//为了计算家庭人数 int father[N]; int findFather(int x) { while (x != father[x])x = father[x]; return x; } void Union(int a, int b) { int faA = findFather(a); int faB = findFather(b); if (faA > faB)father[faA] = faB; if (faA < faB)father[faB] = faA; } bool cmp(root a, root b) { if (a.numpeople == 0 || b.numpeople == 0)return a.numpeople > b.numpeople; else if (a.area * 1.00 / a.numpeople == b.area * 1.00 / b.numpeople) return a.id < b.id; else return a.area * 1.00 / a.numpeople > b.area * 1.00 / b.numpeople; } void initial() { for (int i = 0;i < N;i++) { father[i] = i; property[i].num = property[i].eara = 0; ans[i].numpeople = ans[i].area = ans[i].num = 0; } } int main() { int n, i, j; scanf("%d", &n); initial(); int owner, fid, mid; for (i = 0;i < n;i++) { scanf("%d%d%d", &owner, &fid, &mid); exist[owner] = true; if (fid >= 0) { exist[fid] = true; Union(owner, fid); } if (mid >= 0) { exist[mid] = true; Union(owner, mid); } int numchild, child; scanf("%d", &numchild); for (j = 0;j < numchild;j++) { scanf("%d", &child); exist[child] = true; Union(owner, child); } scanf("%d%d", &property[owner].num, &property[owner].eara); } for (i = 0;i < N;i++) { if (exist[i]) { int fa = findFather(i); ans[fa].numpeople++; ans[fa].id = fa; ans[fa].num += property[i].num; ans[fa].area += property[i].eara; } } sort(ans, ans + N, cmp); int numfamily = 0; for (i = 0;i < N && ans[i].numpeople;i++)numfamily++; printf("%d\n", numfamily); for (i = 0;i < numfamily;i++) { printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].numpeople, ans[i].num * 1.0 / ans[i].numpeople, ans[i].area * 1.0 / ans[i].numpeople); } return 0; }

 

/*第二次写*/ #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<algorithm> using namespace std; #define MAX 10000 struct own { double area = 0, estate = 0; }people[MAX]; struct familiy { double area = 0, estate = 0; int id, num = 0; }; vector<familiy>ans; int father[MAX], n, m, idmap[MAX] = { 0 }; int findfather(int x) { while (x != father[x])x = father[x]; return x; } void Union(int a, int b) { int FaA = findfather(a), FaB = findfather(b); if (FaA < FaB)father[FaB] = FaA; else if (FaA > FaB)father[FaA] = FaB; } bool cmp(familiy a, familiy b) { if (a.area / a.num * 1.0 == b.area / b.num * 1.0)return a.id < b.id; else return a.area / a.num * 1.0 > b.area / b.num * 1.0; } int main() { int i, j, k, ownid, baba, mama, child; scanf("%d", &n); for (i = 0; i < MAX; i++)father[i] = i; for (i = 0; i < n; i++) { scanf("%d%d%d%d", &ownid, &baba, &mama, &k); idmap[ownid] = 1; if (baba != -1) { Union(ownid, baba); idmap[baba] = 1; } if (mama != -1) { Union(ownid, mama); idmap[mama] = 1; } for (j = 0; j < k; j++) { scanf("%d", &child); idmap[child] = true; Union(ownid, child); } scanf("%lf%lf", &people[ownid].estate, &people[ownid].area); } for (i = 0; i < MAX; i++) { if (idmap[i] > 0) { baba = findfather(i); for (j = 0; j < ans.size(); j++) if (ans[j].id == baba)break; if (j == ans.size()) { familiy temp; temp.id = baba; temp.num = 0; ans.push_back(temp); } ans[j].num++; ans[j].area += people[i].area; ans[j].estate += people[i].estate; } } sort(ans.begin(), ans.end(), cmp); printf("%d\n", ans.size()); for (i = 0; i < ans.size(); i++) printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].num, ans[i].estate / ans[i].num, ans[i].area / ans[i].num); return 0; }