1114 Family Property（25 分）

并查集
注意在计算totsets时遍历a数组就可以，计算人数是从0到maxn遍历，因为不是每一个人有财产和土地

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int father[maxn];
bool isroot[maxn];
struct node {
    int id;
    double mestate, area;
}a[maxn];
int findfather(int x)
{
    int a = x;
    while (x != father[x])x = father[x];
    while (a != father[a])
    {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int x, int y)
{
    int fx = findfather(x);
    int fy = findfather(y);
    if (fx != fy)
    {
        if (fx < fy)father[fy] = fx;
        else father[fx] = fy;
    }
}

struct fam {
    int m, id;
    double totsets, totarea;
    bool valid;
    bool operator<(const fam&x)const
    {
        return valid == true && x.valid == true ? totarea / m == x.totarea / x.m ? id<x.id : totarea / m>x.totarea / x.m : valid > x.valid;
    }
}ans[maxn];
int main()
{
    int n;
    for (int i = 0; i < maxn; i++)father[i] = i;
    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        int id, f, m;
        scanf("%d %d %d", &id, &f, &m);
        if (f != -1)Union(id, f);
        if (m != -1)Union(id, m);
        int k, child;
        scanf("%d", &k);
        while (k--)
        {
            scanf("%d", &child);
            Union(id, child);
        }
        a[i].id = id;
        scanf("%lf%lf", &a[i].mestate, &a[i].area);
        
    }
    for (int i = 0; i < n; i++)
    {
        int f = findfather(a[i].id);
        ans[f].id = f;
        ans[f].totsets += a[i].mestate;
        ans[f].totarea += a[i].area;
        ans[f].valid = true;
        isroot[f] = true;
    }
    for (int i = 0; i < maxn; i++)
    {
        int f = findfather(i);
        ans[f].m++;
    }
    int cnt = 0;
    for (int i = 0; i < maxn; i++)cnt += isroot[i];
    sort(ans, ans + maxn);
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++)
    {
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].m, ans[i].totsets / ans[i].m, ans[i].totarea / ans[i].m);
    }
    return 0;
}