A1114 Family Property (25 point(s))

并查集应用

1. 原文

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* *C**h**i**l**d*1⋯*C**h**i**l**d**k* *M**e**s**t**a**t**e* `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; Child**i‘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

2. 解析

并查集串联id-father-mother-children

set记录出现的值

遍历set 统计id的father的总estate，area，count

遍历set vector中存入每个id的id ，count，estate，area，fatherid

按fatherid降序，id降序，相同fatherid的最小id存入vector ans

按平均area，id排序，输出

3. AC代码

#include<cstdio>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
map<int,int> estate,area,cnt;
set<int> family;
int father[100000]={};
void init()
{
	for (int i = 0; i < 100000; ++i)
	{
		father[i]=i;
	}
}
int findFather(int x)
{
	int a=x;
	while(x!=father[x]){
		x=father[x];
	}
	while(a!=father[a]){
		int z=a;
		a=father[a];
		father[z]=x;
	}
	return x;
}
void together(int a,int b){
	int fatherA=findFather(a);
	int fatherB=findFather(b);
	if (fatherA!=fatherB)
	{
		father[fatherA]=fatherB;
	}
}
struct node{
	int id,count,father;
	double area,estate;
};
bool cmp1(node a,node b){
	if (a.father!=b.father){
		return a.father<b.father;
	}
	else{
		return a.id<b.id;
	}
}
bool cmp(node a,node b){

	if (a.area!=b.area)
	{
		return a.area>b.area;
	}else{
		return a.id<b.id;
	}
}
vector<node> v;
int main()
{
	init();
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int id;
		scanf("%d",&id);
		family.insert(id);
		int fa,mo;
		scanf("%d%d",&fa,&mo);
		if (fa!=-1)
		{
			together(id,fa);
			family.insert(fa);
		}
		if (mo!=-1)
		{
			together(id,mo);
			family.insert(mo);
		}
		int k;
		scanf("%d",&k);
		int child;
		for (int i = 0; i < k; ++i)
		{
			scanf("%d",&child);
			together(id,child);
			family.insert(child);
		}
		scanf("%d%d",&estate[id],&area[id]);
	}
	for (set<int>::iterator i = family.begin(); i != family.end(); ++i)
	{
		cnt[findFather(*i)]++;
		if (findFather(*i)==*i)
		{
			continue;
		}
		estate[findFather(*i)]+=estate[*i];
		area[findFather(*i)]+=area[*i];
	}
	for (set<int>::iterator i = family.begin(); i != family.end(); ++i)
	{
		node temp;
		temp.id=*i;
		temp.count=cnt[findFather(*i)];
		temp.estate=estate[findFather(*i)]*1.0/cnt[findFather(*i)];
		temp.area=area[findFather(*i)]*1.0/cnt[findFather(*i)];
		temp.father=findFather(*i);
		v.push_back(temp);
	}
	sort(v.begin(),v.end(),cmp1);
	// for (int i = 0; i < v.size(); ++i)
	// {
	// 	printf("%d %d\n", v[i].id,v[i].father);
	// }
	vector<node> ans;
	int first=0;
	for (int i = 1; i < v.size(); ++i)
	{
		if (v[i].father!=v[first].father)
		{
			ans.push_back(v[first]);
			first=i;
		}	
	}
	ans.push_back(v[first]);
	sort(ans.begin(),ans.end(),cmp);
    printf("%lu\n",ans.size());
    for (int i = 0; i < ans.size(); ++i)
    {
    	printf("%04d %d %.3f %.3f\n", ans[i].id,ans[i].count,ans[i].estate,ans[i].area);
    }
	return 0;
}