题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805068539215872
题意:给定n个人的信息,包括其编号,父母以及孩子的编号,以及其名下的房产数量和房产面积,要求有多少个家族,并列出每个家族的最小编号,家庭人数,家庭人均房产数量和人均房产面积。
思路:算法部分就是简单的并查集,但数据处理等方面还挺复杂,一定要仔细。首先用个data结构体数组来存储输入的每个人的信息,用node结构体来存储每个家族的信息,其中包括该家族最小成员编号,人数,人均房产数量和人均房产面积,其中flag涌来标识是否存在,因为数据量不大,可以暴力处理,就是要注意编码细节。输入人的信息时,将他和其父母孩子合并,并使祖先的编号最小,用vis数组标记该编号是否出现。合并之后遍历n个人,将其1房产信息都加入到家族结构体中,最后还要排序,先按人均房产面积降序排列,再按编号升序排列。
AC代码:
#includeusing 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 yy.area;}int main(){ scanf("%d",&n); for(int i=0;i<10000;++i) root[i]=i; for(int i=0;i