1114 Family Property (25分)

题目链接：1114 Family Property (25分)

题意

给出N个人的 自己的id, 父亲的id，母亲的id,孩子个数，孩子id,房产数量，拥有房子总面积。求N个人一共有多少个家庭关系，输出每组家庭的 成员最小编号， 家庭人员个数，家庭平均房产数量，家庭平均土地面积，按照家庭平均土地面积递减排序，若相同则按照成员最小id递增排序。

分析

考察并查集。将每个人的id,父母id,孩子id并入集合，根为id最小的那个，且根值为集合个数的相反数。在设置一个家庭结构体，用来存放输出的答案。遍历完n个人后得到集合，且每组集合的根元素为集合中的id最小的。以每个集合根元素的id作为答案结构体的下标，然后在遍历每个人，找到所属集合根id，将资产情况存入家庭结构体中，然后在对家庭结构体按照题目要求排序。家庭个数为集合个数，也为排序后家庭总人数不为0的个数。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10000;
typedef struct Person{
    int id;int father, mother;vector<int> child;int eNum;double area;Person() {
    father = mother = -1;eNum = 0;area = 0;}
}Person;
typedef struct Family{
    int id, pNum;int eNum;double aNum, eavg, areaAvg;}Family;
Person p[maxn];
Family f[maxn];
bool cmp(Family f1, Family f2) {
    if (f1.areaAvg != f2.areaAvg)return f1.areaAvg > f2.areaAvg;return f1.id < f2.id;
}
int father[maxn];
void Union(int a, int b);
int findRoot(int x);
int main(int argc, char** argv) {
    int n, id, cnum, k = 0;scanf("%d", &n);for (int i = 0; i < maxn; i++)father[i] = -1;for (int i = 0; i < n; i++) {
    scanf("%d %d %d %d", &p[i].id, &p[i].father, &p[i].mother, &cnum);if (p[i].father != -1)Union(p[i].id, p[i].father);if (p[i].mother != -1)Union(p[i].id, p[i].mother);for (int j = 0; j < cnum; j++) {
    int cid;scanf("%d", &cid);Union(p[i].id, cid);}scanf("%d%lf", &p[i].eNum, &p[i].area);}for (int i = 0; i < n; i++) {
    int root = findRoot(p[i].id);f[root].id = root;f[root].pNum = -father[root];f[root].aNum += p[i].area;f[root].eNum += p[i].eNum;f[root].eavg = 1.0 * f[root].eNum / f[root].pNum; // 家庭平均地产数f[root].areaAvg = f[root].aNum / f[root].pNum; // 家庭平均地面积}sort(f, f + maxn, cmp);for (; f[k].pNum != 0; k++);printf("%d\n", k);for (int i = 0; i < k; i++) {
    printf("%04d %d %.3f %.3f\n", f[i].id, f[i].pNum, f[i].eavg, f[i].areaAvg);}return 0;
}
int findRoot(int x) {
    while (father[x] >= 0)x = father[x];return x;
}
// 将小值作为根，且根值为集合个数的负数
void Union(int a, int b) {
    int fa = findRoot(a);int fb = findRoot(b);if (fa > fb) {
    int t = father[fa];father[fa] = fb;father[fb] += t;} else if (fa < fb) {
    int t = father[fb];father[fb] = fa;father[fa] += t;}
}