跟着柳婼学姐学习的笔记ヾ（≧▽≦*）o
原题目： 1114 Family Property (25 分).
题意
计算家族资产。给出每个人的家庭成员及其名下房产，计算家族成员人数、他们房产的平均面积和平均房产数量。
给出人数N。接着N行，给出每人及其父母的ID（四位数，若去世则ID为-1），孩子个数k以及孩子们的ID，房产总数M以及房产总面积。
① 输出家族数目，
② 每个家族中最小的ID、总人数M、平均房产套数和平均面积（都精确到3位小数）（优先按平均面积的递减顺序输出，其次按ID递增的顺序）。
分析
- 题意分析：需要算家族数量，即所给每个人的家庭信息存在交叉，需要将同家族的人并到一个集合中——用 并查集——写好三个基本操作。
- 将个人结点按家族合并在一起：
① 用一个结构体数组data接收N个人的数据，顺便实现并查集的合并Union操作——特别地，让ID小的作根结点；
②为了后面统计每个家庭的人数，用数组visit标记所有出现过的结点（静态数组的随机访问性）。 - 统计家族数据：
① 用另一个结构体数组ans记录家族数据。
② 遍历N个人，通过findFather找根结点（所处家族），以对应地录入该家族根结点，统计房产数量和面积；并设置标记flag，方便后面统计家族个数。
③ 遍历所有人（编号可能从0000到9999即最多共10000人），统计家族人数以及家族数量。
④再次遍历所有人，这时有了家族数量，就可以计算平均值了。 - 输出：① 用sort+cmp按要求排序；② 四位数ID在输入时不用特别处理，只要输出时注意补0就好了——%04d。
知识点
- 并查集
- 静态数组的随机访问性
- sort + cmp
注意点
四位数ID在输出时需注意补0。
CODE
#include <iostream>
#include <algorithm>
using namespace std;
struct DATA{ //个人数据
int id, fid, mid;
int cid[10];
int num, area;
}data[1005];
struct node{ //家族数据
int id, people;
double num, area;
bool flag = false;
}ans[10000];
int father[10000];
bool visit[10000];
//并查集基本操作
int findFather(int x);
void Union(int a, int b);
//排列输出顺序
bool cmp(node a, node b){
if ( a.area!=b.area )
return a.area>b.area;
else
return a.id<b.id;
}
int main()
{
int n, k, cnt = 0;
cin >> n;
for ( int i=0; i<10000; i++ )
father[i] = i; //初始化并查集
//生成家族
for ( int i=0; i<n; i++ ){
cin >> data[i].id >> data[i].fid >> data[i].mid;
cin >> k;
visit[data[i].id] = true; //计算家庭人数——标记所有出现过的结点
//将未离世的父母以及孩子们并入家族中
if ( data[i].fid!=-1 ){
visit[data[i].fid] = true;
Union(data[i].fid, data[i].id);
}
if ( data[i].mid!=-1 ){
visit[data[i].mid] = true;
Union(data[i].mid, data[i].id);
}
for ( int j=0; j<k; j++ ){
cin >> data[i].cid[j];
visit[data[i].cid[j]] = true;
Union(data[i].cid[j], data[i].id);
}
cin >> data[i].num >> data[i].area;
}
//家族数据
for ( int i=0; i<n; i++ ){
int id = findFather(data[i].id); //家族根结点
ans[id].id = id; //家族根结点
ans[id].num += data[i].num; //计算家族房产数
ans[id].area += data[i].area; //计算家族总房产面积
ans[id].flag = true; //以计算共有多少个家族（防止ID为0）
}
//统计家族人数和家族数量
for ( int i=0; i<10000; i++ ){
if ( visit[i] )
ans[findFather(i)].people++; //找根结点以统计同根的人数
if ( ans[i].flag )
cnt++; //统计家族数量
}
//计算每个家族的两个平均值
for ( int i=0; i<10000; i++ ){
if ( ans[i].flag ){
// ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
ans[i].num /= ans[i].people;
ans[i].area /= ans[i].people;
}
}
//排序后输出
sort(ans, ans+10000, cmp); //注意：这时候全部都要参与排序，排完待输出数据才会到数组前面
cout << cnt << endl;
for ( int i=0; i<cnt; i++ ){
printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
}
return 0;
}
int findFather(int x){
while( x!=father[x] )
x = father[x];
return x;
}
void Union(int a, int b){
int faA = findFather(a);
int faB = findFather(b);
//让ID小的作根结点
if ( faA>faB )
father[faA] = faB;
else if ( faA<faB )
father[faB] = faA;
}