摘要
Title: L2-007 家庭房产 (25 分)
Tag: 并查集
Memory Limit: 64 MB
Time Limit: 1000 ms

L2-007 家庭房产 (25 分)

题意

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

遇到维护集合类的问题，主题思路还是并查集
- 首先，先存下有关系的边，通过id记录其他信息
- 其次，先将所有点初始化，初始每个集合的大小为1，进行并查集操作，将记录的边的两点合并
  - ps: 注意最后输出的是较小的id，所以合并时可以采用大的连向小的
  - ps: 千万别忘了0
  - 并更新所有信息
- 然后，查找所有节点，满足出现过且是根节点的节点，push到答案数组中
- 最后根据题目要求对其进行排序
- 最后输出即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-04-20 16:30:11
* @FilePath: \ACM\GPLT\L2-007.CPP
* @LastEditTime: 2022-04-20 17:14:52
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MP make_pair
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0);
#define DEBUG(X) cout << #X << ": " << X << endl;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

const int N = 1e5 + 10;

int p[N], c[N], hn[N], hs[N], st[N];
struct sa
{
    int a, b;
} g[N];

struct Family
{
    int id, cnt, hn, hs;
};

int cnt;

int find(int x)
{
    if (x != p[x])
    {
        p[x] = find(p[x]);
    }
    return p[x];
}

signed main()
{
    IOS;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int id, fa, ma, k;
        cin >> id >> fa >> ma >> k;
        st[id] = 1;
        if (fa != -1)
            g[cnt++] = {id, fa}, st[fa] = 1;
        if (ma != -1)
            g[cnt++] = {id, ma}, st[ma] = 1;
        for (int j = 1; j <= k; ++j)
        {
            int son;
            cin >> son;
            g[cnt++] = {id, son};
            st[son] = 1;
        }
        cin >> hn[id] >> hs[id];
    }
    for (int i = 0; i < N; ++i)
        p[i] = i, c[i] = 1;
    for (int i = 0; i < cnt; ++i)
    {
        int pa = find(g[i].a), pb = find(g[i].b);
        if (pa != pb)
        {
            if (pb > pa)
                swap(pa, pb);
            p[pa] = pb;
            c[pb] += c[pa];
            hn[pb] += hn[pa];
            hs[pb] += hs[pa];
        }
    }

    vector<Family> f;
    for (int i = 0; i < N; ++i)
    {
        if (p[i] == i && st[i])
        {
            f.push_back({i, c[i], hn[i], hs[i]});
        }
    }
    sort(f.begin(), f.end(), [&](Family a, Family b) {
        if (a.hs * b.cnt != b.hs * a.cnt)
            return a.hs * b.cnt > b.hs * a.cnt;
        return a.id < b.id;
    });
    printf("%lld\n", SZ(f));
    for (auto [id, cnt1, hn1, hs1] : f)
    {
        printf("%04lld %lld %.3lf %.3lf\n", id, cnt1, 1.0 * hn1 / cnt1, 1.0 * hs1 / cnt1);
    }

    return 0;
}

L2-007 家庭房产 (25 分)

题意

思路

代码