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 Mestate 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; Mestate 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 AVGsets AVGarea
where ID is the smallest ID in the family; M is the total number of family members; AVGsets is the average number of sets of their real estate; and AVGarea 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
题目大意第一行给定数据的条数，接着按照顺序给出：
本人编号 父亲编号(-1表示去世) 母亲编号(-1表示去世) 孩子数量 孩子1编号 孩子2编号 .... 房产数量 房产总面积
只要两个人有关系（无论差多少辈），这两个人就是一家人，要求计算一家人的人均房产拥有数量和人均房产面积，并按照人均面积的降序输出。如果存在并列，按照编号顺序进行排序。
这道题是一道并查集类问题，在并查集的Union操作中，将编号大的附着到编号小的集合上即可。
具体代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
typedef struct {
int father; //爸爸
int estate; //房子总大小
int est_cnt; //房产个数
int men_cnt; //成员数量
} node;
typedef struct {
int id;
int men_cnt;
double avg_set;
double avg_area;
} ans_node;
const node blank = {-1, 0, 0, 1};
const int maxn = 10010;
node S[maxn]; //并查集
int Find(int root){
if(root == -1) return -1;
if(S[root].father != -1)
return Find(S[root].father);
return root;
}
bool cmp(ans_node a, ans_node b){
return a.avg_area != b.avg_area ? a.avg_area > b.avg_area : a.id < b.id;
}
void Union(int &root1, int root2){
root1 = Find(root1), root2 = Find(root2);
if(root1 == root2) return ;
if(root1 < root2){ //如果节点1 < 节点2，则将节点2依附在节点1上
S[root2].father = root1;
S[root1].estate += S[root2].estate;
S[root1].est_cnt+= S[root2].est_cnt;
S[root1].men_cnt+= S[root2].men_cnt;
S[root2].estate = S[root2].est_cnt = S[root2].men_cnt = 0;
}else{ //如果节点2 < 节点1，则将节点1依附在节点2上，并修改root1
S[root1].father = root2;
S[root2].estate += S[root1].estate;
S[root2].est_cnt+= S[root1].est_cnt;
S[root2].men_cnt+= S[root1].men_cnt;
S[root1].estate = S[root1].est_cnt = S[root1].men_cnt = 0;
root1 = root2;
}
}
int main(){
fill(S, S + maxn, blank);
int cnt;
cin >> cnt;
for(int i = 0; i < cnt; i++){
int root, ChildCnt, estate_cnt, estate, id;
cin >> root;
root = Find(root);
for(int _ = 0; _ < 2; _++){
cin >> id;
id = Find(id);
if(id != -1) Union(root, id);
}
cin >> ChildCnt;
for(int _ = 0; _ < ChildCnt; _++){
cin >> id;
id = Find(id);
Union(root, id);
}
cin >> estate_cnt >> estate;
S[root].est_cnt += estate_cnt;
S[root].estate += estate;
}
vector<ans_node> ans;
for(int i = 0; i < maxn; i++){
if(S[i].father == -1 && S[i].est_cnt){
ans_node tmp;
tmp.id = i;
tmp.men_cnt = S[i].men_cnt;
tmp.avg_set = 1.0 * S[i].est_cnt / S[i].men_cnt;
tmp.avg_area= 1.0 * S[i].estate / S[i].men_cnt;
ans.push_back(tmp);
}
}
sort(ans.begin(), ans.end(), cmp);
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i++)
printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].men_cnt, ans[i].avg_set, ans[i].avg_area);
return 0;
}才不是，放屁
?上面这句话是坐在博主右边，博主最喜欢的ybb打的