1114. Family Property (25)

//给定 id id的父亲 id的母亲（-1表示过世） k id的k个孩子 房产的数量 房产的面积
//求每个家庭（用最小的id存储）房产的总数 平均房产数量和面积（平均保留三位）
//排序：平均面积的降序 tie id的增序
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node0 {
    int id, fid, mid, num, area;
    int cid[10];
}data[1001];
struct node {
    int id, people;
    double num, area;
    bool flag = false;
}ans[10000];
vector<int> father(10000);//存放i的父节点的位置
vector<bool> visited(10000);
int find(int x){//找到x的根节点
    while (x != father[x])
        x = father[x];
    return x;
}
void Union(int a, int b){
    a = find(a);
    b = find(b);
    if(a > b) father[a] = b;
    else father[b] = a;
}
bool cmp(node &a, node &b){
    if(a.area == b.area) return a.id < b.id;
    else return a.area > b.area;
}

int main(){
    int n, k, cnt = 0;
    cin >> n;
    for (int i = 0; i < 10000; i++)
        father[i] = i;//初始化每一个节点的父节点为本身
    for (int i = 0; i < n; i++) {
        cin >> data[i].id >> data[i].fid >> data[i].mid >> k;
        visited[data[i].id] = true;//记录存在该结点
        if (data[i].fid != -1) {
            visited[data[i].fid] = true;
            Union(data[i].fid, data[i].id);
        }
        if (data[i].mid != -1) {
            visited[data[i].mid] = true;
            Union(data[i].mid, data[i].id);
        }
        for (int j = 0; j < k; j++) {
            cin >> data[i].cid[j];
            visited[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        cin >> data[i].num >> data[i].area;
    }
    for (int i = 0; i < n; i++) {
        int id = find(data[i].id);//找祖先节点
        ans[id].id = id;//祖先节点为答案节点
        ans[id].num += data[i].num;//同一家族的房子数加和
        ans[id].area += data[i].area;
        ans[id].flag = true;//记录存在该答案结点
    }
    for (int i = 0; i < 10000; i++) {
        if(visited[i]) ans[find(i)].people++;
        if(ans[i].flag) cnt++;
    }
    for (int i = 0; i < 10000; i++) {
        if(ans[i].flag){
            ans[i].num = ans[i].num * 1.0 / ans[i].people;
            ans[i].area = ans[i].area * 1.0 / ans[i].people;
        }
    }
    sort(ans, ans + 10000, cmp);
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++) {
        printf("%04d %d %.3lf %.3lf\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    }
    return 0;
}