1114 family property (25 points)

The main idea of the topic ： Given the relationship of each family member , We need to ask for the number of people in each family , Per capita number of real estate units , Area per capita . Output by per capita real estate area in descending order , If equal, press id Output in ascending order (id Is the smallest in every family id)

At first glance, it is a topic of joint search , What needs to be output is the minimum id, So we need to minimize id Build a tree for the root node .

The title is not difficult. , Change the meaning of the question to find the number of connected blocks , And the number of points in each connected block , And update the information of the real estate .

I stepped on the hole , I didn't initialize the number of points in the connected block 0000 This number is included ,debug For a long time ...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10000;
typedef pair<int,int> PII;
int p[N],siz[N],st[N],L,id,fa,ma,est,ar,tt,cnt,ch;
vector<PII>area(N);
struct node
{
	int id,sum;
	double avgnum,avgare;
	bool operator < (const node &W)
	{
		if(W.avgare != avgare) return avgare > W.avgare;
		return id < W.id;
	}
};
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
void solve(int a,int b)
{
	a = find(a),b = find(b);
	if(a != b) 
	{    
		if(a < b) swap(a,b);// Give Way id The smallest becomes the parent node 
		p[a] = b,siz[b] += siz[a];
		area[b].first += area[a].first,area[b].second += area[a].second;
	}
}
int main()
{
	cin >> tt;
	vector<PII>e(N);
	for(int k = 0; k < tt; k ++)
	{
		cin >> id >> fa >> ma;
		st[id] = true;
		if(fa != -1) e[cnt ++] = {id,fa};
		if(ma != -1) e[cnt ++] = {id,ma};
		cin >> L;
		while(L --)
		{
			cin >> ch;
			e[cnt ++] = {id,ch};
		}
		cin >> est >> ar;
		area[id] = {est,ar};
	}
	for(int i = 0; i < N; i ++) p[i] = i,siz[i] = 1;// initialization 
	for(int i = 0; i < cnt; i ++)
	{
		int a = e[i].first,b = e[i].second;
		st[b] = true;
		solve(a,b);
	}
	vector<node>v;
	for(int i = 0 ; i < N; i ++)
	{     
		if(st[i] && p[i] == i)// Parent node 
		v.push_back({i,siz[i],(double)area[i].first*1.0/siz[i],(double)area[i].second*1.0/siz[i]});
	}
	sort(v.begin(),v.end());
	cout << v.size() << '\n';
	for(auto it : v) 
		printf("%04d %d %.3lf %.3lf\n",it.id,it.sum,it.avgnum,it.avgare);
	return 0;
}