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 (≤). 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) 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两个代码，仅供参考：
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
struct Node
{
int ID, nums = ;
double ss = 0.0, aa = 0.0;
};
int n;
double num[] = { 0.0 }, area[] = { 0.0 };//房子数量//房子面积
int mark[];//标记属于哪个家族
vector<set<int>>sets();//记录每个家庭有多少人
vector<Node*>res;
void combin(int my, int other)//合并家族
{
for (auto ptr = sets[other].begin(); ptr != sets[other].end(); ++ptr)//将其他成员进行同化
{
mark[*ptr] = my;
sets[my].insert(*ptr);
}
sets[other].clear();//删除其他成员的标记
}
int main()
{
cin >> n;
fill(mark, mark + , -);
for (int i = ; i < n; ++i)
{
int my, parent, k, child, nn, aa;
cin >> my;
if (mark[my] == -)//还未标记是哪个家族
{
mark[my] = my;//就以自己为标记
sets[mark[my]].insert(my);
}
for (int i = ; i < ; ++i)//添加父母
{
cin >> parent;
if (parent == -)
continue;
if (mark[parent] == -)//家人未标记
{
mark[parent] = mark[my];
sets[mark[my]].insert(parent);
}
else if (mark[parent] != - && mark[parent] != mark[my])//家人与自己标记不同
combin(mark[my], mark[parent]);//将家人同化为自己标记
}
cin >> k;
while (k--)
{
cin >> child;
if (mark[child] == -)//孩子未标记
{
mark[child] = mark[my];
sets[mark[my]].insert(child);
}
else if (mark[child] != - && mark[child] != mark[my])//孩子与自己标记不同
combin(mark[my], mark[child]);//将孩子同化为自己标记
}
cin >> nn >> aa;
num[my] = nn;
area[my] = aa;
}
for (int i = ; i < sets.size(); ++i)
{
if (sets[i].empty())
continue;
Node* temp = new Node;
temp->ID = *sets[i].begin();
temp->nums = sets[i].size();
for (auto ptr = sets[i].begin(); ptr != sets[i].end(); ++ptr)
{
temp->aa += area[*ptr];
temp->ss += num[*ptr];
}
temp->ss /= temp->nums;
temp->aa /= temp->nums;
res.push_back(temp);
}
sort(res.begin(), res.end(), [](Node*a, Node*b) {
if (abs(a->aa - b->aa) < 0.0001)
return a->ID < b->ID;
else
return a->aa > b->aa; });
cout << res.size() << endl;
for (auto v : res)
printf("%04d %d %0.3f %0.3f\n", v->ID, v->nums, v->ss, v->aa);
return ;
}
#include<bits/stdc++.h>
using namespace std;
struct Estate{//存储集合最小id、集合结点个数num、集合总sets、集合总area
int id,num=;
double sets=0.0,area=0.0;
};
bool cmp(const Estate&e1,const Estate&e2){//比较函数
return e1.area!=e2.area?e1.area>e2.area:e1.id<e2.id;
}
int father[];//并查集底层数组
int findFather(int x){//查找根节点
if(x==father[x])
return x;
int temp=findFather(father[x]);
father[x]=temp;
return temp;
}
void unionSet(int a,int b){//合并两个集合
int ua=findFather(a),ub=findFather(b);
if(ua!=ub)
father[max(ua,ub)]=min(ua,ub);//以小的id作为根节点
}
unordered_map<int,pair<double,double>>idEstate;
unordered_map<int,Estate>familyEstate;
int main(){
int N;
scanf("%d",&N);
iota(father,father+,);
while(N--){//读取数据并合并相关集合
int id,f,m,k,a;
scanf("%d%d%d%d",&id,&f,&m,&k);
if(f!=-)
unionSet(id,f);
if(m!=-)
unionSet(id,m);
while(k--){
scanf("%d",&a);
unionSet(id,a);
}
scanf("%lf%lf",&idEstate[id].first,&idEstate[id].second);//记录id和对应的sets、area
}
for(int i=;i<;++i){//遍历并查集数组
int temp=findFather(i);
if(temp!=i)//根节点不等于本身
++familyEstate[temp].num;//递增根节点下集合的结点个数
if(idEstate.find(i)!=idEstate.cend()){//累加集合的总sets、总area
familyEstate[temp].sets+=idEstate[i].first;
familyEstate[temp].area+=idEstate[i].second;
}
}
vector<Estate>v;
for(auto i=familyEstate.begin();i!=familyEstate.end();++i){//将familyEstate中的值搬迁到vector中,并更新相关信息
(i->second).id=i->first;
++(i->second).num;//集合下结点个数没有统计根节点，所以要+1
(i->second).sets/=(i->second).num;
(i->second).area/=(i->second).num;
v.push_back(i->second);
}
sort(v.begin(),v.end(),cmp);//排序
printf("%d\n",v.size());
for(int i=;i<v.size();++i)
printf("%04d %d %.3f %.3f\n",v[i].id,v[i].num,v[i].sets,v[i].area);
return ;
}