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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
double estate[], area[];
int father[], familyNum[], tb[];
bool cmp(int a, int b){
if(area[a] != area[b])
return area[a] > area[b];
else return a < b;
}
int findFather(int x){
int temp = x;
while(x != father[x]){
x = father[x];
}
int temp2;
while(temp != x){
temp2 = father[temp];
father[temp] = x;
temp = temp2;
}
return x;
}
void merge(int a, int b){
if(a == - || b == -)
return;
int af = findFather(a);
int bf = findFather(b);
if(af == bf)
return;
if(af > bf)
swap(af, bf);
father[bf] = af;
}
int main(){
int N;
scanf("%d", &N);
int id, idf, idm, child;
int chiN;
for(int i = ; i < ; i++){
estate[i] = ;
area[i] = ;
father[i] = i;
familyNum[i] = ;
tb[i] = ;
}
for(int i = ; i < N; i++){
cin >> id >> idf >> idm >> chiN;
tb[id] = tb[idf] = tb[idm] = ;
merge(id, idf);
merge(id, idm);
int son;
for(int j = ; j < chiN; j++){
cin >> son;
tb[son] = ;
merge(id, son);
}
cin >> estate[id] >> area[id];
}
int cnt = ;
vector<int> ans;
for(int i = ; i < ; i++){
if(tb[i] == ){
int ff = findFather(i);
if(ff != i){
estate[ff] += estate[i];
area[ff] += area[i];
}
familyNum[ff]++;
if(i == ff){
cnt++;
ans.push_back(i);
} }
}
for(int i = ; i < ; i++){
if(tb[i] == && father[i] == i){
int Num = familyNum[i];
area[i] = area[i] / (double)Num;
estate[i] = estate[i] / (double)Num;
}
}
sort(ans.begin(), ans.end(), cmp);
printf("%d\n", cnt);
for(int i = ; i < ans.size(); i++){
printf("%04d %d %.3f %.3f\n", ans[i], familyNum[ans[i]], estate[ans[i]], area[ans[i]]);
}
cin >> N;
return ;
}
总结：
1、由于一个人既有双亲又有N多个孩子，所以用树形结构肯定不行。只能用并查集或者图搜索。
2、并查集：并查集仅仅对父母、子女的关系进行合并处理。房子数、面技数、家庭人口等先不计算，仅仅存在每个人各自的对应数组中。由于序号不是连续的1到N，因此father数组中会有很多无效节点，需要一个tb数组在输入的时候就记录哪些是有效的节点。 在并查集处理完家庭关系之后，对father数组再次遍历，当遇到非根节点时，查找到他对应的根节点，并把房子、面积、等累加至根节点对应的数组中。
3、由于要求输出的id为家族中最小id，所以在两个root合并时，要将更小的root作为新的root。