L2-007 家庭房产

分数 25

作者 陈越

单位 浙江大学

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

输入格式：

输入第一行给出一个正整数N（≤1000），随后N行，每行按下列格式给出一个人的房产：

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

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

输出格式：

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

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

其中人均值要求保留小数点后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

 

并查集：

最开始是往并查集的思想上想的，但最终没有想出一个合理的解决方案，又感觉有点像图，就用图的遍历解决，（但我后面写的时候，写成了树，即我图也没建出来），所以毫无疑问，得到了WA。中午睡了一觉之后，再写此题，突然就想出了并查集的解决方案。emm，脑袋不够用了。

我这个并查集稍显繁琐，因为一不小心，就会得出错误答案。CSDN看了一个哥们的博客，先不处理每个家族的人数，房产套数及总面积，用set存储每个人的编号，会自动去重，然后得出每个家族最小编号，最后处理信息，简便许多。

图的遍历应该也是可以写的，不过有点麻烦。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

struct Node //存储输入的节点信息
{
    int fath;
    int flag;
    int pres;
    int cnt,sum;
    
    Node()
    {
        fath = -1;  //初始化每个节点的父节点为-1
        flag = 0;   //如果是家族中编号最小的人就为1，初始化为0；
        pres = 1;   //起初每个家族中至少存在自己，只是这个家族存不存在我们另说；
        cnt = sum = 0; //起初每个家族的房产套数和总面积都为0；
    }
};

struct Node2    //结果结点
{
    int minid , pres ;  //最小编号及家族总人数
    double cnt,sum;   //房产套数及总面积
    
    bool operator < (const Node2 &a) const  //重载运算符
    {
        if(sum != a.sum)
            return sum > a.sum;
        else
            return minid < a.minid;
    }
};

const int maxn = 10010;
Node e[maxn];   //输入信息
vector<Node2> res;  //答案

int find(int u) //并查集
{
    if(e[u].fath == -1)
        return u;
    else
        return find(e[u].fath);
}

void Union(int u,int v) //合并u与v这两个结点
{
    int fau = find(u);
    int fav = find(v);
    if(fau != fav)
    {
        int fath,son;
        if(fau < fav)
        {
            fath = fau;
            son = fav;
        }
        else 
        {
            fath = fav;
            son = fau;
        }
        
        e[son].fath = fath; //儿子指向父亲
        e[son].flag = -1;  //儿子结点无效
        e[fath].flag = 1;  //父亲节点有效
        e[fath].pres += e[son].pres; //父亲节点加上儿子结点的人数
        e[fath].cnt += e[son].cnt; //儿子的房产归父亲
        e[fath].sum += e[son].sum; //儿子的房产总面积归父亲
    }
}

void Read()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int id,fat,mot;
        int k;
        cin >> id >> fat >> mot >> k;
        hs[id] = 1;
        
        if(fat != -1)   //父亲存在
            Union(id,fat); 
        if(mot != -1)  //母亲存在
            Union(id,mot);
    
        for(int i=0;i<k;++i)
        {
           int chi;
           cin >> chi;
           Union(id,chi);
        }
        
        int cnt , sum;
        cin >> cnt >> sum;
        int faid = find(id);    //找到家族里最小的编号
        e[faid].cnt += cnt;    //直接相加
        e[faid].sum += sum;
        e[faid].flag = 1;    //此时他就为有效的结点，这句别忘了，如果此时家族中中有
    }                       //id一个人，那么就会造成信息遗漏
}

void Deal()
{
    for(int i=0;i<10000;++i)
        if(e[i].flag == 1)  //结点有效
            res.push_back({i,e[i].pres,e[i].cnt*1.0/e[i].pres,e[i].sum*1.0/e[i].pres});
}


void Print()
{
    sort(res.begin(),res.end());  //排序
    
    cout << res.size() << endl;
    
    for(int i=0;i<res.size();++i)
        printf("%04d %d %.3f %.3f\n",res[i].minid,res[i].pres,res[i].cnt,res[i].sum);
}


int main()
{
    Read();
    
    Deal();
    
    Print();
    
    return 0;
}