L2-007 family real estate (25 points)

subject

Give everyone's family members and their own properties , Please count the population of each family 、 Per capita real estate area and number of real estate units .

Input format ：
The first line of input gives a positive integer N（≤1000）, And then N That's ok , Each line gives a person's property in the following format ：

Number Father mother k children 1 … children k Number of real estate units Total area
The number is unique to everyone 4 Number of digits ; The parent and the parent are the number of the parent corresponding to the number （ If you have passed away , Is displayed -1）;k（0≤k≤5） It's the number of children of the person ; children i Is the number of their child .

Output format ：
First, output the number of families in the first line （ All relatives belong to the same family ）. Then output the information of each family in the following format ：

Minimum number of family members The number of families Per capita number of real estate units Per capita real estate area
The per capita value shall be kept after the decimal point 3 position . Family information is first output in descending order of per capita area , If there is juxtaposition , Then output... In ascending order of member number .

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

analysis

A problem of parallel search set , See code for details ！！！

Reference code ：

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

const int N = 1010, M = 1e4;

int n;
bool st[M]; //  Mark those id There have been 
int p[M];

struct data
{
    
	int id, num, area;
}a[N];

struct stu
{
    
	int id, people;
	double num, area;
	bool flag;
}ans[M];

//  Find the parent node 
int find(int x)
{
    
	while(x != p[x]) x = p[x];
	return x;
}

//  Merge 2 Subtree 
void Union(int x, int y)
{
    
	int fx = find(x);
	int fy = find(y);
	
	if(fx > fy) p[fx] = fy;
	else p[fy] = fx;
}

bool cmp(stu x, stu y)
{
    
	if(x.area != y.area) return x.area > y.area;
	return x.id < y.id;
}

int main()
{
    
	cin >> n;
	rep(i, 0, M) p[i] = i; // Initialize the parent node of all points for itself  
	
	rep(i, 1, n)
	{
    
		int id, d_id, m_id, k, son, num, area;
		cin >> id >> d_id >> m_id;
		st[id] = true;
		
		if(d_id != -1)
		{
    
			st[d_id] = true;
			Union(id, d_id);
		}
		
		if(m_id != -1)
		{
    
			st[m_id] = true;
			Union(id, m_id);
		}
		
		cin >> k;
		while(k--)
		{
    
			cin >> son;
			st[son] = true;
			Union(id, son);
		}
		
		cin >> num >> area;
		a[i] = {
    id, num, area};
	}
	
	rep(i, 1, n)
	{
    
		int id = find(a[i].id);
		ans[id].id = id;
		ans[id].num += a[i].num;
		ans[id].area += a[i].area;
		ans[id].flag = true; //  Number of marked families 
	}
	
	int cnt = 0;
	//  because id The data range is small , Directly enumerate all possible 4 number id, And use the fear and search set to accumulate the family population 
	rep(i, 0, 9999)
	{
    
		if(st[i]) ans[find(i)].people++;
		if(ans[i].flag) cnt++;
	}
	
	rep(i, 0, 9999)
		if(ans[i].flag)
		{
    
			ans[i].num = ans[i].num / ans[i].people;
			ans[i].area = ans[i].area / ans[i].people;
		}
	
	
	sort(ans, ans + M, cmp);
	
	cout << cnt << endl;
	//  Because it is output in descending order according to the average area , So you can output directly after sorting 
	rep(i, 0, cnt - 1)
		printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
	
	return 0;
}