题意：给出每个人的家庭成员信息和自己的房产个数与房产总面积，让你统计出每个家庭的人口数、人均房产个数和人均房产面积。第一行输出家庭个数，随后每行输出家庭成员的最小编号、家庭人口数、人均房产个数、人均房产面积。
并查集，合并的时候编号小的作为父亲节点，最后父亲节点一样的即属于一个家庭，其它都是细节处理没啥好说了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
/*
并查集
*/
const int maxn=+;
int vis[maxn];
struct UF{
int father[maxn];
void init(){
for(int i=;i<maxn;i++){
father[i]=i;
}
}
int find_root(int x){
if(father[x]!=x){
father[x]=find_root(father[x]);
}
return father[x];
}
void Union(int a,int b){
int fa=find_root(a);
int fb=find_root(b);
if(fa!=fb){
father[max(fa,fb)]=min(fa,fb); //最小编号的作为祖先
}
}
}uf; struct Person{
int id;
int dad,mom;
int k;
int child[];
int m_estate;
int area;
}person[maxn]; struct Family{
int minid; //家庭成员最小编号
int m=; //家庭人口数
int m_estate=; //总房产数目
int totarea=; //总房产面积
float AVG_sets; //人均房产个数
float AVG_area; //人均房产面积
bool operator<(const Family tmp)const{
if(AVG_area==tmp.AVG_area){
return minid<tmp.minid;
}
else{
return AVG_area>tmp.AVG_area;
}
}
}family[maxn]; int main()
{
int n,id;
scanf("%d",&n);
uf.init();
memset(vis,,sizeof(vis));
for(int i=;i<maxn;i++)
person[i].id=-;
for(int i=;i<n;i++){
scanf("%d",&id);
person[id].id=id;
scanf("%d %d %d",&person[id].dad,&person[id].mom,&person[id].k);
vis[person[id].id]=; //标记出现过的编号
if(person[id].dad!=-){
uf.Union(id,person[id].dad);
vis[person[id].dad]=;
}
if(person[id].mom!=-){
uf.Union(id,person[id].mom);
vis[person[id].mom]=;
}
for(int j=;j<person[id].k;j++){
scanf("%d",&person[id].child[j]);
uf.Union(id,person[id].child[j]);
vis[person[id].child[j]]=;
}
scanf("%d %d",&person[id].m_estate,&person[id].area);
}
int idArray[maxn];
int cnt=;
for(int i=;i<maxn;i++){
if(vis[i]==){
idArray[cnt++]=i; //出现过的编号存起来
}
}
memset(vis,,sizeof(vis));
int u,fa;
for(int i=;i<cnt;i++){
u=idArray[i];
fa=uf.find_root(idArray[i]);
vis[fa]=; //标记父亲节点
family[fa].minid=fa;
family[fa].m++;
if(person[u].id!=-){
family[fa].totarea+=person[u].area;
family[fa].m_estate+=person[u].m_estate;
}
}
int familyNum=;
for(int i=;i<maxn;i++){
if(vis[i]){
familyNum++;
family[i].AVG_sets=family[i].m_estate*1.0f/family[i].m;
family[i].AVG_area=family[i].totarea*1.0f/family[i].m;
}
}
sort(family,family+maxn);
printf("%d\n",familyNum);
for(int i=;i<familyNum;i++){
printf("%04d %d %.3f %.3f\n",family[i].minid,family[i].m,family[i].AVG_sets,family[i].AVG_area);
}
return ;
}