L2-007 家庭房产

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
using namespace std;

const int MAXN = 10000; // 最大编号范围，编号是4位数，范围是0000-9999

struct Person {
    int id; // 个人编号
    int father; // 父亲编号
    int mother; // 母亲编号
    vector<int> children; // 子女编号列表
    int numHouses; // 房产套数
    double area; // 房产总面积
};

struct Family {
    int minId; // 家庭成员的最小编号
    int size; // 家庭人口数
    double totalHouses; // 家庭总房产套数
    double totalArea; // 家庭总房产面积
};

int parent[MAXN]; // 并查集的父节点数组
map<int, Person> persons; // 存储所有人的信息，键为编号
map<int, bool> exists; // 记录哪些编号存在

// 并查集的查找函数，带路径压缩
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

// 并查集的合并函数
void unionSets(int x, int y) {
    if (x == -1 || y == -1) return; // 忽略无效编号（如-1）
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY; // 合并两个集合
    }
}

// 比较函数，用于家庭排序
bool compareFamilies(const Family& a, const Family& b) {
    double avgAreaA = a.totalArea / a.size; // 家庭A的人均面积
    double avgAreaB = b.totalArea / b.size; // 家庭B的人均面积
    if (avgAreaA != avgAreaB) {
        return avgAreaA > avgAreaB; // 按人均面积降序
    }
    return a.minId < b.minId; // 如果人均面积相同，按最小编号升序
}

int main() {
    int N;
    cin >> N; // 输入人数

    // 初始化并查集
    for (int i = 0; i < MAXN; i++) {
        parent[i] = i; // 每个节点的父节点初始化为自己
    }

    // 输入数据
    for (int i = 0; i < N; i++) {
        Person p;
        cin >> p.id >> p.father >> p.mother; // 输入编号、父亲编号、母亲编号
        int k;
        cin >> k; // 输入子女数量
        p.children.resize(k);
        for (int j = 0; j < k; j++) {
            cin >> p.children[j]; // 输入每个子女的编号
        }
        cin >> p.numHouses >> p.area; // 输入房产套数和总面积
        persons[p.id] = p; // 将个人信息存入map
        exists[p.id] = true; // 标记该编号存在
        if (p.father != -1) exists[p.father] = true; // 标记父亲编号存在
        if (p.mother != -1) exists[p.mother] = true; // 标记母亲编号存在
        for (int child : p.children) exists[child] = true; // 标记子女编号存在

        // 合并家庭成员
        unionSets(p.id, p.father); // 合并本人和父亲
        unionSets(p.id, p.mother); // 合并本人和母亲
        for (int child : p.children) {
            unionSets(p.id, child); // 合并本人和子女
        }
    }

    // 统计家庭信息
    map<int, Family> families;
    for (auto& pair : exists) {
        int id = pair.first; // 当前编号
        int root = find(id); // 找到该编号的根节点（家庭代表）
        if (families.find(root) == families.end()) {
            // 如果该家庭尚未被统计，初始化家庭信息
            families[root] = {id, 0, 0, 0};
        }
        families[root].size++; // 家庭人口数加1
        if (id < families[root].minId) {
            families[root].minId = id; // 更新家庭成员的最小编号
        }
        if (persons.find(id) != persons.end()) {
            // 如果该编号有房产信息，累加到家庭总房产套数和总面积
            families[root].totalHouses += persons[id].numHouses;
            families[root].totalArea += persons[id].area;
        }
    }

    // 转换为结果数组
    vector<Family> result;
    for (auto& pair : families) {
        result.push_back(pair.second); // 将家庭信息存入结果数组
    }

    // 排序
    sort(result.begin(), result.end(), compareFamilies); // 按人均面积降序排序

    // 输出结果
    cout << result.size() << endl; // 输出家庭数量
    for (const Family& f : result) {
        // 输出家庭成员的最小编号、人口数、人均房产套数、人均房产面积
        cout << setw(4) << setfill('0') << f.minId << " "
             << f.size << " "
             << fixed << setprecision(3) << f.totalHouses / f.size << " "
             << f.totalArea / f.size << endl;
    }

    return 0;
}

1. 代码解析