This time, you are supposed to help us collect the data for family-owned property. Given each person‘s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.
Each input file contains one test case. For each case, the first line gives a positive integer N (≤). Then N lines follow, each gives the infomation of a person who owns estate in the format:
ID Father Mother k Child?1???Child?k?? M?estate?? Area
where ID is a unique 4-digit identification number for each person; Father and Mother are the ID‘s of this person‘s parents (if a parent has passed away, -1 will be given instead); k (0) is the number of children of this person; Child?i??‘s are the ID‘s of his/her children; M?estate?? is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.
For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:
ID M AVG?sets?? AVG?area??
where ID is the smallest ID in the family; M is the total number of family members; AVG?sets?? is the average number of sets of their real estate; and AVG?area?? is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID‘s if there is a tie.
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
题意：
寻找一个家族人员的最小编号，总人数，AVGsets， AVGarea。
思路：
将每一个家族中的人归并的一个子集中，这道题要求寻找最小的编号因此Union的时候要使编号小的成为编号大的祖先结点。
Code：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 vector<int> fa(10005, 0); 6 7 int findFather(int x) { 8 int a = x; 9 while (x != fa[x]) { 10 x = fa[x]; 11 } 12 // 路径压缩 13 while (a != fa[a]) { 14 int z = a; 15 a = fa[a]; 16 fa[z] = x; 17 } 18 return x; 19 } 20 21 void Union(int x, int y) { 22 int faX = findFather(x); 23 int faY = findFather(y); 24 if (faX < faY) 25 fa[faY] = faX; 26 else 27 fa[faX] = faY; 28 } 29 30 struct Family { 31 int index = 0; 32 double sum_estate = 0; 33 double sum_area = 0; 34 double AVGarea = 0; 35 double AVGsets = 0; 36 bool haveMerged = false; 37 set<int> people; 38 }; 39 40 bool cmp(Family x, Family y) { 41 if (x.AVGarea == y.AVGarea) 42 return x.index < y.index; 43 else 44 return x.AVGarea > y.AVGarea; 45 } 46 47 int main() { 48 int n; 49 cin >> n; 50 Family fam[10005]; 51 for (int i = 0; i < 10005; ++i) fa[i] = i; 52 for (int i = 0; i < n; ++i) { 53 int id, father, mather, nums, child, estate, area; 54 cin >> id >> father >> mather >> nums; 55 set<int> people; 56 people.insert(id); 57 if (father != -1) { 58 people.insert(father); 59 Union(id, father); 60 } 61 if (mather != -1) { 62 people.insert(mather); 63 Union(id, mather); 64 } 65 for (int j = 0; j < nums; ++j) { 66 cin >> child; 67 people.insert(child); 68 Union(id, child); 69 } 70 cin >> estate >> area; 71 int index = findFather(id); 72 fam[index].sum_estate += estate; 73 fam[index].sum_area += area; 74 fam[index].index = index; 75 for (int p : people) fam[index].people.insert(p); 76 } 77 vector<Family> ans; 78 for (int i = 0; i < 10005; ++i) { 79 if (fam[i].sum_estate > 0) { 80 int index = findFather(i); 81 fam[index].haveMerged = true; 82 if (i != index) { 83 fam[index].sum_area += fam[i].sum_area; 84 fam[index].sum_estate += fam[i].sum_estate; 85 fam[index].index = index; 86 for (int j : fam[i].people) fam[index].people.insert(j); 87 } 88 } 89 } 90 for (int i = 0; i < 10005; ++i) { 91 if (fam[i].haveMerged) ans.push_back(fam[i]); 92 } 93 for (auto& it : ans) { 94 it.AVGarea = it.sum_area / it.people.size(); 95 it.AVGsets = it.sum_estate / it.people.size(); 96 } 97 sort(ans.begin(), ans.end(), cmp); 98 cout << ans.size() << endl; 99 for (auto it : ans) { 100 printf("%04d %d %.3f %.3f\n", it.index, it.people.size(), it.AVGsets, 101 it.AVGarea); 102 } 103 return 0; 104 }
原文：https://www.cnblogs.com/ruruozhenhao/p/12774099.html