PAT甲级真题 1114 Family Property (25分) C++实现 (并查集）

题目

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.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother k Child1 … Childk 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<=k<=5) is the number of children of this person; Childi’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.

Output Specification:

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.

Sample Input:

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

Sample Output:

3 8888 1 1.000 1000.000 0001 15 0.600 100.000 5551 4 0.750 100.000

思路

用并查集划分出各个家庭，在Union时直接将id号小的作为父亲，即家庭的代表。

用set记录出现过的id（省得后面从0-10000遍历），遍历set找出各个家庭的代表，顺便将家族财产都记录到代表名下。

将这些代表的财产记录到结构体数组中，再排序即可。

坑

注意id号可以取到0，判断id是否合法时要用if (id >= 0)，否则最后两个测试点会报错。

代码

#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; vector<int> fa(10001), M(10001), A(10001); struct Property { int id; int num; double M; double A; }; bool cmp(Property p1, Property p2) { return p1.A == p2.A ? p1.id<p2.id : p1.A>p2.A; } void init() { for (int i = 1; i < fa.size(); i++) { fa[i] = i; } } int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); } void Union(int x, int y) { int fx = find(x); int fy = find(y); if (fx < fy) { fa[fy] = fx; } else { fa[fx] = fy; } } int main() { init(); set<int> ids; //记录所有出现过的id int n; cin >> n; for (int i = 0; i < n; i++) { int id; vector<int> family; for (int j = 0; j < 3; j++) { cin >> id; if (id >= 0) { family.push_back(id); ids.insert(id); } } int k; cin >> k; for (int j = 0; j < k; j++) { cin >> id; family.push_back(id); ids.insert(id); } for (int j = 1; j < family.size(); j++) { Union(family[0], family[j]); } cin >> M[family[0]] >> A[family[0]]; } vector<int> fathers; vector<Property> pros(10001); for (auto id : ids) { int father = find(id); if (father == id) { fathers.push_back(id); pros[id].id = id; } pros[father].num++; pros[father].M += M[id]; pros[father].A += A[id]; } cout << fathers.size() << endl; vector<Property> fatherPros(fathers.size()); for (int i = 0; i < fathers.size(); i++) { fatherPros[i] = pros[fathers[i]]; fatherPros[i].M = fatherPros[i].M / fatherPros[i].num; fatherPros[i].A = fatherPros[i].A / fatherPros[i].num; } sort(fatherPros.begin(), fatherPros.end(), cmp); for (int i = 0; i < fatherPros.size(); i++) { printf("%04d %d %.3f %.3f\n", fatherPros[i].id, fatherPros[i].num, fatherPros[i].M, fatherPros[i].A); } return 0; }