并查集

// The average numbers must be accurate up to 3 decimal places. 
//The families must be given in descending order of their average areas,
//and in ascending order of the ID's if there is a tie.
//info 信息n.  tie平局  nonegative integer非负整数
//ascending order升序  in descending 递减

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

using namespace std;

const int N = 10010;

int n;
int p[N];
int c[N],hc[N],ha[N];//c人数，fc房子的数量，fa房子的面积
int st[N];//每个id是否存在，记录一下，方便后面遍历id

struct E{
    int a,b;
}e[N];

struct Family{
    int id,c;
    double hc,ha;
};

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

int cmp(Family a,Family b)
{
    if(a.ha/a.c != b.ha/b.c) return a.ha/a.c > b.ha/b.c;
    else return a.id<b.id;
}

int main()
{
    cin>>n;
    int m = 0;
    for(int i = 0; i<n; i++)
    {
        int id,father,mother,k;
        cin>>id>>father>>mother>>k;

        st[id] = true;
        if(father != -1) e[m++] = {id,father};
        if(mother != -1) e[m++] = {id,mother};

        for(int j = 0; j<k; j++)
        {
            int son;
            cin>>son;
            e[m++] = {id,son};
        }

        cin>>hc[id]>>ha[id];
    }

    for(int i = 0; i<N; i++) p[i] = i,c[i] = 1;

    for(int i = 0; i<m; i++)
    {
        int a = e[i].a,b = e[i].b;

        st[a] = st[b] = true;
        int pa = find(a),pb = find(b);
        if(pa!=pb)
        {
            if(pb > pa) swap(pa,pb);//让id小的放在集合头部，会比较方便
            c[pb] += c[pa];
            hc[pb] += hc[pa];
            ha[pb] += ha[pa];
            p[pa] = pb;//集合合并
        }
    }
    vector<Family> family;
    for(int i = 0; i<N; i++)//枚举所有的id
        if(st[i] && p[i] == i)//家庭代表，祖宗元素
        {
            family.push_back({i,c[i],hc[i],ha[i]});
        }

    sort(family.begin(),family.end(),cmp);

    cout<<family.size()<<endl;
    for(auto f:family)
        printf("%04d %d %.3lf %.3lf\n",f.id,f.c,f.hc/f.c,f.ha/f.c);
    return 0;
}