L2-007 家庭房产

后面每个家族最小编号不知道怎么处理，就没做出来。
然后去翻阅blog，发现差不多是两种方案，第一种在融合的时候让编号小的当根节点，那么最终这个家族的祖先就是编号最小的节点。
第二种就是融合的时候没处理，到后面处理（看起来好麻烦）。
下面就是第一种写法（注:结构体中的id没用，可以删了）。

#include <bits/stdc++.h>
using namespace std;
struct node {
	int id,rs;//编号，家庭人数
	double mj,ts;//面积 套数
} s[10000];
int parent[10000],deep[10000];
int isexist[10000];//编号是否存在
bool cmp(int a,int b) {
	if(s[a].mj!=s[b].mj) return s[a].mj>s[b].mj;
	return a<b;
}
int getf(int x) {
	int y=x;
	while(parent[y]!=-1) {
		y=parent[y];
	}
	return y;
}
void merge(int x,int y) {
	int p1=getf(x);
	int p2=getf(y);
	if(p1==p2) return;
	if(p1<p2) {
		swap(p1,p2);
	}
	parent[p1]=p2;//p2是小的那个 让小的那个当父亲 最后这个家族的祖先就是最小索引的节点
}
int main() {
	memset(parent,-1,sizeof(parent));
	memset(deep,0,sizeof(deep));
	int n;
	cin>>n;
	for(int i=0; i<n; i++) {
		int no,p1,p2,count,ch,ts,mj;
		cin>>no>>p1>>p2>>count;
		isexist[no]=1;
		if(p1!=-1) {
			merge(no,p1);
			isexist[p1]=1;
		}
		if(p2!=-1) {
			merge(no,p2);
			isexist[p2]=1;
		}
		for(int j=0; j<count; j++) {
			cin>>ch;
			isexist[ch]=1;
			merge(no,ch);
		}
		cin>>s[no].ts>>s[no].mj;//该编号的房产套数 和总资产
	}
	for(int i=0; i<10000; i++) {//汇总家族的人数 房产套数和总资产
		if(isexist[i]) {
			int parent=getf(i);
			if(parent==i) {
				s[parent].rs+=1;
			} else {
				s[parent].mj+=s[i].mj;
				s[parent].ts+=s[i].ts;
				s[parent].rs+=1;
			}
		}
	}
	vector<int> ans;//存放每个家族的祖先的编号
	for(int i=0; i<10000; i++) {
		if(isexist[i]) {
			int parent=getf(i);
			if(parent==i) {
				s[i].mj/=s[i].rs;//计算人均
				s[i].ts/=s[i].rs;
				ans.push_back(i);
			}
		}
	}
	//对ans进行排序
	cout<<ans.size()<<'\n';
	sort(ans.begin(),ans.end(),cmp);
	for(int i=0; i<ans.size(); i++) {
		printf("%04d %d %.3lf %.3lf\n",ans[i],s[ans[i]].rs,s[ans[i]].ts,s[ans[i]].mj);
	}
	return 0;
}