pta l2-7（家庭房产）

题目链接：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[];

}a[];

struct node{

    int idm,pp,flag;

    double num,area;

}fam[];

int root[],vis[],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=;i<;++i)

        root[i]=i;

    for(int i=;i<n;++i){

        scanf("%d%d%d%d",&a[i].id,&a[i].fa,&a[i].ma,&a[i].k);

        for(int j=;j<a[i].k;++j)

            scanf("%d",&a[i].ch[j]);

        scanf("%d%d",&a[i].num,&a[i].area);

        vis[a[i].id]=;

        if(a[i].fa!=-)

            vis[a[i].fa]=,Union(a[i].id,a[i].fa);

        if(a[i].ma!=-)

            vis[a[i].ma]=,Union(a[i].id,a[i].ma);

        for(int j=;j<a[i].k;++j)

            vis[a[i].ch[j]]=,Union(a[i].id,a[i].ch[j]);

    }

    for(int i=;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=;

    }

    for(int i=;i<;++i){

        if(vis[i]) ++fam[getr(i)].pp;

        if(fam[i].flag) ++res;

    }

    for(int i=;i<;++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+,cmp);

    printf("%d\n",res);

    for(int i=;i<res;++i)

        printf("%04d %d %.3f %.3f\n",fam[i].idm,fam[i].pp,fam[i].num,fam[i].area);

    return ;

}