题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805068539215872
题意：给定n个人的信息，包括其编号，父母以及孩子的编号，以及其名下的房产数量和房产面积，要求有多少个家族，并列出每个家族的最小编号，家庭人数，家庭人均房产数量和人均房产面积。
思路：算法部分就是简单的并查集，但数据处理等方面还挺复杂，一定要仔细。首先用个data结构体数组来存储输入的每个人的信息，用node结构体来存储每个家族的信息，其中包括该家族最小成员编号，人数，人均房产数量和人均房产面积，其中flag涌来标识是否存在，因为数据量不大，可以暴力处理，就是要注意编码细节。输入人的信息时，将他和其父母孩子合并，并使祖先的编号最小，用vis数组标记该编号是否出现。合并之后遍历n个人，将其1房产信息都加入到家族结构体中，最后还要排序，先按人均房产面积降序排列，再按编号升序排列。
AC代码：
#include<bits/stdc++.h> using namespace std; struct data{ int id,fa,ma,k,num,area; int ch[6]; }a[1005]; struct node{ int idm,pp,flag; double num,area; }fam[10005]; int root[10005],vis[10005],n,res; int getr(int k){ if(root[k]==k) return k; else return root[k]=getr(root[k]); } void Union(int x,int y){ int xr=getr(x),yr=getr(y); if(xr<yr) root[yr]=xr; else root[xr]=yr; } bool cmp(node xx,node yy){ if(xx.area==yy.area) return xx.idm<yy.idm; else return xx.area>yy.area; } int main(){ scanf("%d",&n); for(int i=0;i<10000;++i) root[i]=i; for(int i=0;i<n;++i){ scanf("%d%d%d%d",&a[i].id,&a[i].fa,&a[i].ma,&a[i].k); for(int j=0;j<a[i].k;++j) scanf("%d",&a[i].ch[j]); scanf("%d%d",&a[i].num,&a[i].area); vis[a[i].id]=1; if(a[i].fa!=-1) vis[a[i].fa]=1,Union(a[i].id,a[i].fa); if(a[i].ma!=-1) vis[a[i].ma]=1,Union(a[i].id,a[i].ma); for(int j=0;j<a[i].k;++j) vis[a[i].ch[j]]=1,Union(a[i].id,a[i].ch[j]); } for(int i=0;i<n;++i){ int idr=getr(a[i].id); fam[idr].idm=idr; fam[idr].num+=a[i].num; fam[idr].area+=a[i].area; fam[idr].flag=1; } for(int i=0;i<10000;++i){ if(vis[i]) ++fam[getr(i)].pp; if(fam[i].flag) ++res; } for(int i=0;i<10000;++i) if(fam[i].flag){ fam[i].num=fam[i].num*1.0/(fam[i].pp*1.0); fam[i].area=fam[i].area*1.0/(fam[i].pp*1.0); } sort(fam,fam+10000,cmp); printf("%d\n",res); for(int i=0;i<res;++i) printf("%04d %d %.3f %.3f\n",fam[i].idm,fam[i].pp,fam[i].num,fam[i].area); return 0; }
原文：https://www.cnblogs.com/FrankChen831X/p/10543298.html