L2-007 家庭房产 题解

L2-007 家庭房产：

思路：

1.因为要根据题给的隐藏关系划分家庭，所以并查集

2.合并操作的UNION函数做一些小小的变化，保证根结点是集合中数值最小的

3.记录每个人的房产数，房产总面积，并在最后加到大家庭（集合）的数据中

#include<cstdio>
#include<map>//使用到pair
#include<algorithm>//sort
using namespace std;
typedef pair<float,float> geren;//定义一个名为geren的floa对floa的数据类型
const int N=10010;//编号是四位数
//用于记录划家庭（集合）后每个家庭的情况
struct jiaxinxi{
    int hao;
    int ren=0;//后面记录大家庭人数时包括了根结点自己，所以此处为0
    float junnum=0;
    float juns=0;
}xinxi[N];
int n;
int father[N];
//本题中由题目给出出现的编号，并不是从1~n所有的数都出现，所以使用一个bool的数组记录出现的数字编号
bool isroot[N],chuxian[N]={false};
void init( ){
    for(int i=0;i<N;i++){
        father[i]=i;
        isroot[i]=false;
    }
}
int findfather(int x){
    while(x!=father[x]){
        x=father[x];
    }
    return x;
}
void UNION(int a,int b){
    int fa=findfather(a);
    int fb=findfather(b);
    if(fa!=fb){
        /*由于题目要求输出每个家庭中最小的编号，所以在合并集合时让数值相对小的编
        号作为根结点，这样最后划分完后每个集合的根结点就是该集合中的数值最小的编号*/
        if(fa<fb)
            father[fb]=fa;
        else
            father[fa]=fb;
    }
}
//结构体比较函数
bool cmp(jiaxinxi a,jiaxinxi b){
    if(a.juns!=b.juns) return a.juns>b.juns;//面积先大后小
    else return a.hao<b.hao;//编号先小后大
}
int main(){
    int i,j,numk,numj=0,ji,fu,mu,zi;
    geren zijixinxi[N];//用于记录每个人的房产数，房产总面积
    scanf("%d",&n);
    init();
    for(i=0;i<n;i++){
        //自己，父亲，母亲，儿子数量
        scanf("%d %d %d %d",&ji,&fu,&mu,&numk);
        chuxian[ji]=true;//标记编号出现
        if(fu!=-1){
            UNION(ji,fu);
            chuxian[fu]=true;
        }
        if(mu!=-1){
            UNION(ji,mu);
            chuxian[mu]=true;
        }
        for(j=0;j<numk;j++){
            scanf("%d",&zi);
            UNION(ji,zi);
            chuxian[zi]=true;
        }
        scanf("%f %f",&zijixinxi[ji].first,&zijixinxi[ji].second);
    }
    //对出现的编号，寻找他们的根结点并标记
    for(i=0;i<N;i++){
        if(chuxian[i]){
            isroot[findfather(i)]=true;
        }
    }
    //寻找根结点，记数并记录在大家庭情况的结构体数组中
    for(i=0;i<N;i++){
        if(chuxian[i]){
            if(isroot[i]){
                xinxi[numj++].hao=i;
            }
        }
    }
    for(i=0;i<N;i++){
        if(chuxian[i]){
            for(j=0;j<numj;j++){
                //如果当前编号是这个大家庭中的人
                if(findfather(i)==xinxi[j].hao){
                    xinxi[j].ren++;
                    xinxi[j].junnum+=zijixinxi[i].first;
                    xinxi[j].juns+=zijixinxi[i].second;
                    break;//集合间不会有交集，执行完直接跳出
                }
            }
        }
    }
    //计算平均值
    for(i=0;i<numj;i++){
        xinxi[i].junnum=xinxi[i].junnum/xinxi[i].ren;
        xinxi[i].juns=xinxi[i].juns/xinxi[i].ren;
    }
    //按题目要求排序
    sort(xinxi,xinxi+numj,cmp);
    //输出
    printf("%d\n",numj);
    for(i=0;i<numj;i++){
        printf("%04d %d %.3f %.3f\n",xinxi[i].hao,xinxi[i].ren,xinxi[i].junnum,xinxi[i].juns);
    }
}