L2-007 家庭房产（并查集）

题目：

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式：

输入第一行给出一个正整数

编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积

其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（

输出格式：

首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

输入样例：

10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100

输出样例：

3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

并查集：

最初了解并查集是看的这位哥们的博客：，下面我简单概括一下。

一般题目类型：1、解决有几个联通分支的问题。2、判断两个结点是否在一个联通分支。3、将两个联通分支连起来等等。。。。其实这些问的都差不多，都是要按题目要求把结点划分成不同的连通分支。

基本构成：

1、int pre[ ]

这个数组记录了每个结点的父结点。数组元素的值就是数组下标表示的结点的父结点。初始化时所有结点的父结点都是它自身，也就是元素的值等于元素下标。

2、int find(int x){

while(x!=pre[x]) //如果该结点的父结点不是它自身

　　　　x=pre[x]; //那么就继续找它的父结点的父结点

　 return x;}

查找函数：用于查找结点的父结点。

3、void Union(int x,int y){

　　int fx=find(x); //找到x的根结点

　　int fy=find(y); //找到y的根结点

　　if(fx!=fy) //如果x和y的根结点不相同（x和y不属于同一个联通分支）

　　　　pre[fx]=fy; //就把x的根结点的父结点改为y的根结点

　　}

　　合并函数：用于将两个结点所在的连通分支合为一个。通过将其中一个连通分支的根结点的父结点改为另一个连通分支的根结点。pre[fx]=fy;也可以根据题意做变动，比如这题要求输出家庭成员的最小编号，那么就要把编号大的根结点并入编号小的一边，这样直接输出一个连通分支的根结点就是这个联通分支中编号最小的了。

并查集并查集，两个函数就是一个并，一个查，再加上一个存放父结点的数组。一般来说，一个并查集对应三个操作：初始化+查找根结点函数+合并集合函数。

思路：

?两个结构体数组，?个data?来接收数据，接收的时候顺便实现了并查集的操作union，另?个数组ans?来输出最后的答案，因为要计算家庭?数，所以?visit标记所有出现过的结点，对于每个结点的?结点，people++统计?数。标记flag == true，计算true的个数cnt就可以知道?共有多少个家庭。排序后输出前cnt个就是所求答案。

上代码：

#include 
#include 
#include 
using namespace std;
struct DATA{
    int id,fid,mid,num,area;
    int cid[10];
}data[1005];
struct ANS{
    int id,people;//家庭成员的最小编号 家庭人口数
    double num,area;//人均房产套数 人均房产面积
    bool flag=false;//统计true的个数可以知道一共有多少个家庭    
}ans[10000];
int father[10000];//编号都是四位数,表示下标的父节点 
bool visit[10000];//下标所表示的编号是否有人 
int find(int x)//找到x的根结点
{ 
    while(x!=father[x])
        x=father[x];
    return x;    
}
void Union(int x,int y)//将x和y合并到一颗树中
{
    int fx=find(x);
    int fy=find(y);
    if(fx>fy)//要求输出家庭成员的最小编号， 所以根节点应该最小 
    {
        father[fx]=fy;
    }else if(fx<fy){
        father[fy]=fx;
    } 
}
bool cmp(ANS a,ANS b)//家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
{
    if(a.area!=b.area) return a.area>b.area;
    else return a.id<b.id;
}
int main()
{
     int n,k,cnt=0;
     cin>>n;
     for(int i=0;i<10000;i++)
     {
         father[i]=i;//初始化所有结点的父节点都为自身 
     }
     for(int i=0;i)
     {
         cin>>data[i].id>>data[i].fid>>data[i].mid>>k;
         visit[data[i].id]=true;
         if(data[i].fid!=-1)
         {
             visit[data[i].fid]=true;
            Union(data[i].fid,data[i].id);//如果此人的父亲没有过世，就将其合并到家族    
         }
         
         if(data[i].mid!=-1)
         {
             visit[data[i].mid]=true;
             Union(data[i].mid,data[i].id);
         }
         for(int j=0;j//把孩子也加入家族 
        {
             cin>>data[i].cid[j];
             visit[data[i].cid[j]]=true;
             Union(data[i].cid[j],data[i].id);
         }    
         cin>>data[i].num>>data[i].area;
    }
    for(int i=0;i//统计 
    {
        int id=find(data[i].id);
        ans[id].id=id;//整个家族的根结点 
        ans[id].num+=data[i].num;//整个家族的房产套数 
        ans[id].area+=data[i].area;//整个家族的房产面积 
        ans[id].flag=true;//用于统计家族数 
     } 
     for(int i=0;i<10000;i++)
     {
         if(visit[i])//每找到一个人 
             ans[find(i)].people++;//就将他所在的家族人数加一 
        if(ans[i].flag)//每找到一个家族 
            cnt++; //家族数加一 
     }
     for(int i=0;i<10000;i++)//计算每个家族的人均房产套数和房产面积 
     {
         if(ans[i].flag)
         {
             ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
             ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
         }
      } 
      sort(ans,ans+10000,cmp); 
      printf("%d\n", cnt);
     for(int i = 0; i < cnt; i++)
         printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people,ans[i].num, ans[i].area);
    return 0;
 }

GPLT