PAT甲级-1114 Family Property

题目

题目大意

共有n个户主，每个户主的房产按照“ 户主id 父亲id 母亲id 孩子个数 孩子的id 房产数 房产面积 ”的格式给出。如果父亲或母亲不存在，值为-1。每个户主及其父亲母亲孩子可以构成一个家庭，不同户主如果有相同的家人，那么就可以将两家联系起来组成一个大家庭。要求输出家庭数和家庭id（取家庭中的最小id），平均房产数，平均房产面积。输出按照平均房产面积从大到小排序，如果相同，按id从小到大排序。

思路

从一堆人中组团并求团的个数，并查集。由题可知，户主母亲父亲孩子不管是谁的id都是等价的，它们的共同祖先（家庭id）就是这群人中的最小id（题目中规定的）。每个家庭中的人可以合并，不同家庭中的人也可合并，合并的条件就是看两个人的家庭id是否相同以及一个人是否存在于两个家庭中。pre[]数组即记录每个人对应的家庭id；find()数组找到根节点，即其所属最大家庭的id；combine()合并两个人或集合；init()初始化，完成并查集的建立。另外还需要记录每个人对应的家庭成员数、房产数、房产大小，只有根节点对应的值才有效。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int n;
int pre[10000];  // 并查集，记录前驱节点，为家庭id的最小值
vector<int> num(10000, 1);  // 家庭成员数，初始化为1
int amount[10000] = {0};  // 房产数
int area[10000] = {0};  // 房产大小int find(int a){if (pre[a] == a){return a;}else{return pre[a] = find(pre[a]);}
}  // 找某元素的根节点void combine(int a, int b){int root_a = find(a);int root_b = find(b);if (root_a == root_b){return;}if (root_a < root_b){pre[root_b] = root_a;num[root_a] += num[root_b];amount[root_a] += amount[root_b];area[root_a] += area[root_b];}else{pre[root_a] = root_b;num[root_b] += num[root_a];amount[root_b] += amount[root_a];area[root_b] += area[root_a];}
}  // 合并两个不同的集合void init(){cin >> n;for (int i = 0; i < 10000; i++){pre[i] = i;}  // 初始化pre数组for (int i = 0; i < n; i++){int id, f, m, k, amounts, areas;vector<int> p;cin >> id >> f >> m >> k;p.push_back(id);if (f != -1) p.push_back(f);if (m != -1) p.push_back(m);for (int j = 0; j < k; j++){int child;cin >> child;p.push_back(child);}cin >> amounts >> areas;sort(p.begin(), p.end());for (int j = 0; j < (int)p.size(); j++){combine(p[j], p[0]);}  // 合并每一个家庭成员int root = find(id);amount[root] += amounts;area[root] += areas;  // 累加到一个家庭中的根节点}
}struct family{int id;int total;double avg_amount;double avg_area;
};bool cmp(family x, family y){if (x.avg_area == y.avg_area){return x.id < y.id;}return x.avg_area > y.avg_area;
}int main(){init();vector<family> res;for (int i = 0; i < 10000; i++){if (pre[i] == i && (amount[i] > 0 || area[i] > 0)){res.push_back({i, num[i], amount[i] * 1.0 / num[i], area[i] * 1.0 / num[i]});}}sort(res.begin(), res.end(), cmp);cout << (int)res.size() << endl;for (int i = 0; i < (int)res.size(); i++){printf("%04d %d %.3lf %.3lf\n", res[i].id, res[i].total, res[i].avg_amount, res[i].avg_area);}return 0;
}