PAT甲级1114 Family Property：[C++题解]结构体、并查集、测试点3、4、5有问题的进来！！

本文主要是介绍PAT甲级1114 Family Property：[C++题解]结构体、并查集、测试点3、4、5有问题的进来！！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

来源：acwing

分析:

先建边。读入每家的信息，在本人和父母（如果有的话），本人与子女（如果有的话）之间分别建边。边用结构体来存，边记录两个端点。
遍历每条边，合并集合，分成一个一个家庭。这里的“遍历每条边”，指的是遍历两条边的端点（户主，或父母，或子女）,利用find()函数合并，这里把id大的挂到id小的上面，这样，根结点就是答案所求的户主id。
将每个家庭存入vector，排序输出即可。为此，需要一个Family结构体，里面存户主id，家庭人数c，家庭房子数量hc，家庭房子面积ha，并重载小于号进行排序。

需要注意的点：

用int表示id，不用string。起初想用string来表示id，发现较为麻烦。原因有二，一是用string之后，用并查集之后还需要一步从string到int 的映射，教麻烦。二是题目明确每个id都是4位数，并且各不相同，这是变相地给我们降级难度，提示我们使用int。
家庭户主的id是编号最小的。由于我们是用并查集做的，这就提示我们只维护一个最小的id即可，其他id在统计到各个家庭之后没有什么用。在并查集中，合并的时候把较大的root接到较小的root上，这样得到的root就是最小的root。
前导0的输出，万能C语言！！！由于用int来存的id，如果像0004这样婶儿的，存的只是4，这就考验我们的格式化输出能力。使用printf("%04d",a);含义是以4位宽度输出数a，不足4位的在前面补0！

补充：printf("%4d",id)表示输出宽度为4，且右对齐，不足的在前面补空格。当变量的实际宽度大于4时，输出变量的所有数字.

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010; //边的数量
int n;
int p[N]; //并查集父亲数组
int  c[N];//c[i]表示i这家人的人数 count
int hc[N];//房子数量 house count
int ha[N]; //房子面积 house area
bool st[N];// 户主 和父母，子女分别建边
struct Edge{int a, b;
}e[N];// 一家人放在一个结构体中，排序使用
struct Family{int id ,c ,hc, ha;bool operator<(const Family & t)const{// ha /c , t.ha/t.cif( ha * t.c != c * t.ha) return ha * t.c > c* t.ha;return id < t.id;}
};//并查集找根
int find(int x){if(p[x]!= x) p[x] = find(p[x]);return p[x];
}int main(){cin >>n;int m =0; //表示边数//第一部分： 读入所有输入，并建边for(int i = 0; i < n; i++){int id , father ,mother, k;cin >> id >> father >> mother >>k;//标记id出现过st[id] = true;if(father != -1) e[m++] = {id,father};if(mother != -1) e[m++] = {id,mother};for(int j = 0 ;j< k; j++){int son;cin >> son;e[m++] ={id,son};}cin >> hc[id] >> ha[id]; //房子数量，房子面积}//第二部分：得到每个家庭，并且户主编号最小//并查集初始化for(int i = 0; i<= N; i++) p[i] = i,c[i] =1 ;//i这家人只有1个人//遍历每条边：合并集合：得到每个家庭。for(int i = 0 ; i<m ;i++){int a = e[i].a, b = e[i].b;st[a] = st[b] = true; //标记每个点出现过//一个集合的根结点int pa = find(a),pb = find(b);//合并集合，让根结点大的集合挂到 根结点小的集合上！！//这样根结点就是编号最小的那个！！！//题目要求：ID 是家庭成员中编号最小的成员编号if(pa != pb){if(pb > pa) swap(pa,pb); //让pb成为较小的// 那么pb那个集合的值都要更新：加上pa集合的值//人数 ， 房子数量，房子面积c[pb] += c[pa],hc[pb]+= hc[pa],ha[pb] += ha[pa];//pa集合挂到编号更小pb集合p[pa] = pb; }}// 第三部分：每个家庭的信息存起来，并输出vector<Family> familys;//遍历所有的点，如果之前出现过st[i] == true 并且是集合的根结点p[i] == i//代表i就是一家之主，将该家庭统计到vector中for(int i =0 ;i < N; i++){if(st[i] && p[i] == i)familys.push_back({i,c[i],hc[i],ha[i]});}//排序输出sort(familys.begin(),familys.end());cout<< familys.size()<<endl;for( auto f :familys){printf("%04d %d %.3lf %.3lf\n",f.id, f.c,(double)f.hc/f.c,(double)f.ha/f.c);}
}