PAT 1114. Family Property (25)

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000). Then N lines follow, each gives the infomation of a person who owns estate in the format: ID Father Mother k Child1 … Childk M_estate Area where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0<=k<=5) is the number of children of this person; Childi’s are the ID’s of his/her children;M_estate is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format: ID M AVG_sets AVG_area where ID is the smallest ID in the family; M is the total number of family members; AVG_sets is the average number of sets of their real estate; and AVG_area is the average area. 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.

Sample Input:

10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100

Sample Output:

3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

并查集

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int len = 10010;
int father[len], empty[len], estates[len], areas[len];
vector<struct Family> family;

struct Family {
    int id, m;
    double estate, area;

    Family(int m_id, int m_m, double m_estate, double m_area) {
        id = m_id;
        m = m_m;
        estate = m_estate;
        area = m_area;
    }
};

bool cmp(struct Family a, struct Family b) {
    if (a.area > b.area) return true;
    if (a.area == b.area) {
        return a.id < b.id;
    }
    return false;
}

void init() {
    for (int i = 0; i < len; i++) {
        father[i] = i;
        empty[i] = 1;
        estates[i] = 0;
        areas[i] = 0;
    }
}

int findFather(int x) {
    while (x != father[x]) x = father[x];
    return x;
}

void unionFind(int a, int b) {
    if (b == -1) return;
    int fa = findFather(a), fb = findFather(b);
    if (fa < fb) father[fb] = fa;
    else if (fb < fa) father[fa] = fb;
}

void findFamily() {
    int f[len];
    fill(f, f + len, 0);
    for (int i = 0; i < len; i++) {
        f[findFather(i)]++;
        if (i != findFather(i)) {
            estates[findFather(i)] += estates[i];
            areas[findFather(i)] += areas[i];
        }
    }
    for (int i = 0; i < len; i++) {
        if (!empty[i] && f[i] != 0) {
            struct Family fy(i, f[i], estates[i] * 1.0 / f[i], areas[i] * 1.0 / f[i]);
            family.push_back(fy);
        }
    }
}

int main() {
    init();
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int id = 0, f = 0, m = 0, k = 0;
        scanf("%d %d %d %d", &id, &f, &m, &k);
        unionFind(id, f);
        unionFind(id, m);
        empty[id] = 0;
        if (f != -1) empty[f] = 0;
        if (m != -1) empty[m] = 0;
        for (int j = 0; j < k; j++) {
            int child = 0;
            scanf("%d", &child);
            unionFind(id, child);
            empty[child] = 0;
        }
        int estate = 0, area = 0;
        scanf("%d %d", &estate, &area);
        estates[id] = estate;
        areas[id] = area;
    }
    findFamily();

    sort(family.begin(), family.end(), cmp);
    printf("%lu\n", family.size());
    for (int i = 0; i < family.size(); i++) {
        struct Family t = family[i];
        printf("%04d %d %.3f %.3f\n", t.id, t.m, t.estate, t.area);
    }
    return 0;
}