此文章同步发布在我的CSDN上https://blog.csdn.net/weixin_44385565/article/details/89930332
1114 Family Property (25 分)
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
题目大意：根据给出的数据分类出各个家庭，然后输出家庭个数；接下来输出每个家庭的成员ID（只需输出家庭成员中最小的ID）、成员数量、平均房产数量、平均房产面积，输出顺序为平均房产面积降序、ID升序。
思路：用并查集S给家庭分类，为了方便找出最小的家庭成员ID，对并查集的操作稍作修改，集合元素初始化为对应的下标，若S[X]==X，则X为根，unionSet()函数将大根集合并到小根集合里；家庭成员计数时需要对已经访问过的ID进行标记，防止重复计数，用visit数组标记每个ID。
总结：其实我是比较害怕这类问题的，看起来简单，可是信息一多思考起来就容易混乱，需要很细心很耐心地分析，用不到什么算法知识却超级消耗时间~
1 #include <iostream> 2 #include <vector> 3 #include <unordered_map> 4 #include <algorithm> 5 using namespace std; 6 struct node1 { 7 int ID, fID, mID, k, Me, area; 8 vector <int> child; 9 }; 10 struct node2 { 11 int sumM = 0, sumSets = 0, sumArea = 0; 12 }; 13 struct node3 { 14 int ID, M; 15 float AVGs, AVGa; 16 }; 17 vector <int> S(10000); 18 vector <bool> visit(10000, false); 19 void initialize();//对集合S进行初始化 20 bool cmp(node3 &a, node3 &b);//排序规则 21 int getNum(node1 &a);//获取家庭成员的数量 22 int find(int X); 23 void unionSet(int X, int Y); 24 int main() 25 { 26 int N; 27 scanf("%d", &N); 28 vector <node1> data(N); 29 unordered_map <int, node2> mp; 30 initialize(); 31 for (int i = 0; i < N; i++) { 32 node1 tmp; 33 scanf("%d%d%d%d", &tmp.ID, &tmp.fID, &tmp.mID, &tmp.k); 34 if (tmp.fID != -1) 35 unionSet(tmp.ID, tmp.fID); 36 if (tmp.mID != -1) 37 unionSet(tmp.ID, tmp.mID); 38 if (tmp.k != 0) { 39 for (int j = 0; j < tmp.k; j++) { 40 int cID; 41 scanf("%d", &cID); 42 tmp.child.push_back(cID); 43 unionSet(tmp.ID, cID); 44 } 45 } 46 scanf("%d%d", &tmp.Me, &tmp.area); 47 data[i] = tmp; 48 } 49 for (int i = 0; i < N; i++) { 50 int ID = find(data[i].ID); 51 mp[ID].sumM += getNum(data[i]); 52 mp[ID].sumSets += data[i].Me; 53 mp[ID].sumArea += data[i].area; 54 } 55 vector <node3> ans; 56 for (auto it = mp.begin(); it != mp.end(); it++) { 57 int ID = it->first, 58 M = it->second.sumM; 59 float AVGs = it->second.sumSets*1.0 / M, 60 AVGa = it->second.sumArea*1.0 / M; 61 ans.push_back({ ID,M,AVGs,AVGa }); 62 } 63 sort(ans.begin(), ans.end(), cmp); 64 printf("%d\n", ans.size()); 65 for (int i = 0; i < ans.size(); i++) 66 printf("%04d %d %.3f %.3f\n", ans[i].ID, ans[i].M, ans[i].AVGs, ans[i].AVGa); 67 return 0; 68 } 69 int getNum(node1 &a) { 70 int n = 0; 71 if (!visit[a.ID]) { 72 n++; 73 visit[a.ID] = true; 74 } 75 if ((a.fID != -1 )&& (!visit[a.fID])) { 76 n++; 77 visit[a.fID] = true; 78 } 79 if ((a.mID != -1) && (!visit[a.mID])) { 80 n++; 81 visit[a.mID] = true; 82 } 83 if (a.k != 0) { 84 for (int i = 0; i < a.k; i++) { 85 if (!visit[a.child[i]]) { 86 n++; 87 visit[a.child[i]] = true; 88 } 89 } 90 } 91 return n; 92 } 93 void unionSet(int X, int Y) { 94 int rootX = find(X), 95 rootY = find(Y); 96 if (rootX > rootY) 97 S[rootX] = S[rootY]; 98 else 99 S[rootY] = S[rootX]; 100 } 101 int find(int X) { 102 if (S[X] == X) { 103 return X; 104 } 105 else { 106 return S[X] = find(S[X]);//递归地压缩路径 107 } 108 } 109 void initialize() { 110 for (int i = 0; i < 10000; i++) 111 S[i] = i;//将集合元素初始化为对应的下标，每个集合的根节点就是当前家庭的最小ID 112 } 113 bool cmp(node3 &a, node3 &b) { 114 if (a.AVGa != b.AVGa) 115 return a.AVGa > b.AVGa; 116 else 117 return a.ID < b.ID; 118 }
PAT甲级——1114 Family Property (并查集)
原文：https://www.cnblogs.com/yinhao-ing/p/10828472.html