题目粗心
给定一个人的家庭成员及其房产信息，须要晓得每一个家庭的人数，均匀占地面积和房产数目。
算法思路
这是一道惯例的并查集利用题目，咱们首先应用families数组保留所有的输出集,并在输出的时候记录哪些是输出的成员(应用visited记录)，并且合并那些是一家人的成员，这样就将所有成员都进行了归类在各自的家庭，而后计算每一个家庭的占地总面积和总房产数目，并且应用flag标记以后家庭(在[0,10000]中有意义的家庭)，而后在[0,10000]的所有人中统计所有的家庭成员数目(visited[i]=true的就是)和家庭数目(flag为true的人代表一个家庭)，最初计算房子的均匀面积和数目。
留神点
- 1、在输出的时候families的下标是从0开始到n-1完结，这样不便遍历输出的成员并进行信息计算
- 2、计算房子的均匀面积和数目的时候，得应用总共的信息total_*除以家庭人数，因为该计算过程会执行屡次。
提交后果
AC代码
#include<cstdio>#include<algorithm>#include<vector>using namespace std;struct Family { int ID; int father; int mother; vector<int> children; int estate; int area;} families[1001];// 存储后果集struct Node { int ID; int total_number; double Avg_sets; double Avg_area; int total_sets; int total_area; bool flag;// 标记以后家庭} nodes[10000];bool cmp(const Node &a, const Node &b) { return a.Avg_area != b.Avg_area ? a.Avg_area > b.Avg_area : a.ID < b.ID;}// 统计在[0,10000]中哪些是存在的成员bool visited[10000];// 记录每一个人的先人(可能不在输出中)int father[10000];// 找到x的先人，这里采纳了压缩门路的形式int findFather(int x) { int a = x; while (x != father[x]) { x = father[x]; } while (a != father[a]) { int z = father[a]; father[a] = x; a = z; } return x;}void Union(int a, int b) { int fa = findFather(a); int fb = findFather(b); if (fa < fb) { father[fb] = fa; } else { father[fa] = fb; }}int main() { for (int i = 0; i < 10000; ++i) { father[i] = i; } int n; scanf("%d", &n); Family member; int k; for (int i = 0; i < n; ++i) { scanf("%d %d %d %d", &member.ID, &member.father, &member.mother, &k); int child; for (int j = 0; j < k; ++j) { scanf("%d", &child); member.children.push_back(child); visited[child] = true; Union(member.ID, child); } scanf("%d %d", &member.estate, &member.area); families[i] = member; visited[member.ID] = true; if (member.father != -1) { visited[member.father] = true; Union(member.ID, member.father); } if (member.mother != -1) { visited[member.mother] = true; Union(member.ID, member.mother); } } // 将所有归类的家庭进行计算相干信息 for (int i = 0; i < n; ++i) { int id = findFather(families[i].ID); nodes[id].ID = id; nodes[id].total_area += families[i].area; nodes[id].total_sets += families[i].estate; nodes[id].flag = true; } int num = 0; // 统计家庭成员人数和家庭数目 for (int i = 0; i < 10000; ++i) { if (visited[i]) { int id = findFather(i); ++nodes[id].total_number; } if (nodes[i].flag) { ++num; } } // 计算房子的均匀面积和均匀数目 for (int i = 0; i < 10000; ++i) { if (visited[i]) { int id = findFather(i); nodes[id].Avg_area = nodes[id].total_area*1.0/nodes[id].total_number; nodes[id].Avg_sets = nodes[id].total_sets*1.0/nodes[id].total_number; } } printf("%d\n", num); sort(nodes,nodes+10000,cmp); for(int i=0;i<num;++i){ printf("%04d %d %.3f %.3f\n",nodes[i].ID,nodes[i].total_number,nodes[i].Avg_sets,nodes[i].Avg_area); } return 0;}