关于c++:PAT甲级1114-Family-Property

题目粗心

给定一个人的家庭成员及其房产信息，须要晓得每一个家庭的人数，均匀占地面积和房产数目。

算法思路

这是一道惯例的并查集利用题目，咱们首先应用 families 数组保留所有的输出集, 并在输出的时候记录哪些是输出的成员 (应用 visited 记录)，并且合并那些是一家人的成员，这样就将所有成员都进行了归类在各自的家庭，而后计算每一个家庭的占地总面积和总房产数目，并且应用 flag 标记以后家庭(在[0,10000] 中有意义的家庭)，而后在 [0,10000] 的所有人中统计所有的家庭成员数目 (visited[i]=true 的就是) 和家庭数目(flag 为 true 的人代表一个家庭)，最初计算房子的均匀面积和数目。

留神点

• 1、在输出的时候 families 的下标是从 0 开始到 n - 1 完结，这样不便遍历输出的成员并进行信息计算
• 2、计算房子的均匀面积和数目的时候，得应用总共的信息 total_* 除以家庭人数，因为该计算过程会执行屡次。

提交后果

AC 代码

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

using namespace std;

struct Family {
    int ID;
    int father;
    int mother;
    vector<int> children;
    int estate;
    int area;
} families[1001];

// 存储后果集
struct Node {
    int ID;
    int total_number;
    double Avg_sets;
    double Avg_area;
    int total_sets;
    int total_area;
    bool flag;// 标记以后家庭
} nodes[10000];

bool cmp(const Node &a, const Node &b) {return a.Avg_area != b.Avg_area ? a.Avg_area > b.Avg_area : a.ID < b.ID;}

// 统计在 [0,10000] 中哪些是存在的成员
bool visited[10000];

// 记录每一个人的先人(可能不在输出中)
int father[10000];

// 找到 x 的先人，这里采纳了压缩门路的形式
int findFather(int x) {
    int a = x;
    while (x != father[x]) {x = father[x];
    }
    while (a != father[a]) {int z = father[a];
        father[a] = x;
        a = z;
    }
    return x;
}

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

int main() {for (int i = 0; i < 10000; ++i) {father[i] = i;
    }
    int n;
    scanf("%d", &n);
    Family member;
    int k;
    for (int i = 0; i < n; ++i) {scanf("%d %d %d %d", &member.ID, &member.father, &member.mother, &k);
        int child;
        for (int j = 0; j < k; ++j) {scanf("%d", &child);
            member.children.push_back(child);
            visited[child] = true;
            Union(member.ID, child);
        }
        scanf("%d %d", &member.estate, &member.area);
        families[i] = member;
        visited[member.ID] = true;
        if (member.father != -1) {visited[member.father] = true;
            Union(member.ID, member.father);
        }
        if (member.mother != -1) {visited[member.mother] = true;
            Union(member.ID, member.mother);
        }
    }
    // 将所有归类的家庭进行计算相干信息
    for (int i = 0; i < n; ++i) {int id = findFather(families[i].ID);
        nodes[id].ID = id;
        nodes[id].total_area += families[i].area;
        nodes[id].total_sets += families[i].estate;
        nodes[id].flag = true;
    }
    int num = 0;
    // 统计家庭成员人数和家庭数目
    for (int i = 0; i < 10000; ++i) {if (visited[i]) {int id = findFather(i);
            ++nodes[id].total_number;
        }
        if (nodes[i].flag) {++num;}
    }
    // 计算房子的均匀面积和均匀数目
    for (int i = 0; i < 10000; ++i) {if (visited[i]) {int id = findFather(i);
            nodes[id].Avg_area = nodes[id].total_area*1.0/nodes[id].total_number;
            nodes[id].Avg_sets = nodes[id].total_sets*1.0/nodes[id].total_number;
        }
    }
    printf("%d\n", num);
    sort(nodes,nodes+10000,cmp);
    for(int i=0;i<num;++i){printf("%04d %d %.3f %.3f\n",nodes[i].ID,nodes[i].total_number,nodes[i].Avg_sets,nodes[i].Avg_area);
    }
    return 0;
}