给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
- 输入格式：
输入第一行给出一个正整数N（<=1000），随后N行，每行按下列格式给出一个人的房产：
编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
其中 编号 是每个人独有的一个4位数的编号；父 和 母 分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0<=k<=5）是该人的子女的个数；孩子i是其子女的编号。
- 输出格式：
首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
- 输入样例：
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 - 输出样例：
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000
- 思路
初始时每个人都当做一个家庭people，每个家庭所含元素有编号，父节点编号（初始为自身编号），该家庭最小编号（初始自身编号），家庭人数（初始为1），家庭房产总套数（初始为0），家庭房产总面积（初始为0）
初始家庭数faminum为0
设置一个read数组来标记某个编号是否之前已经录入过了
在读到每个编号时，若它未被录入过则要新建一个家庭，faminum++
find同一般并查集
union两个家庭u，v时把u的父节点设置为v，若u的最小编号更小则更新v的最小，v的家庭房产加上u的，并且faminum--
在读每一行时，要把第一个编号这个人和他的父母孩子做union操作，并且读入该行的房产信息，并且加到第一个编号所属家庭的根上面去
输出时因为有特定的顺序（按平均房产降序，若相同则最小编号升序）
所以我给家庭people类重载了<号，并且把每个家庭的根people放到向量famiR中，然后用了sort排序
把家庭的根放到向量中这一步我采用的是在读数据的时候把每行第一个编号放到一个向量fir中（因为每一行肯定是属于同一个家庭的所以这里一定包含所有家庭了）
设置一个数组来标记某个编号是否以作为根被放到向量中了
循环fir找根，找到未标记过的根就放到famiR中
若找到的根的数目等于之前已经知道的家庭数faminum时就可以退出循环了
啊我写的还是挺麻烦的，一个上午好歹ac了==
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#define N 10000
using namespace std;
class people {
public:
int id;
int fid;
int minid;
int num;
int hnum;
double hs;
void p_Init(int t_id) {
id = t_id;
minid = t_id;
fid = id;//注意这步不要漏
num = 1;
hnum = 0;
hs = 0;
}
friend bool operator<(people a, people b)
{
if ((a.hs*0.1 / a.num) == (b.hs*0.1 / b.num))
return a.minid < b.minid;
return a.hs*0.1 / a.num > b.hs*0.1 / b.num;
}
};
int read[N] = { 0 };
people fami[N];
int faminum=0;
int root[N] = { 0 };//在最后找根的时候判断有没有被当成过根的数组
vector<int> fir;//输入中每行的第一个编号，最后找根的时候用
vector<people> famiR;//每个家庭的根，输出比较的时候用
int findR(int i)
{
if (fami[i].fid != i) {
fami[i].fid = findR(fami[i].fid);
}
return fami[i].fid;
}
void unionF(int v, int u)
{
int vr = findR(v);
int ur = findR(u);
if (vr != ur) {
if (fami[ur].minid<fami[vr].minid) fami[vr].minid = fami[ur].minid;
fami[vr].num += fami[ur].num;
fami[vr].hnum += fami[ur].hnum;
fami[vr].hs += fami[ur].hs;
fami[ur].fid = vr;
--faminum;//每合并一次就要减少一个家庭
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int temp_id, p1, p2, chil, t_hnum, t_hs;
cin >> temp_id;
fir.push_back(temp_id);
if (!read[temp_id]) {
fami[temp_id].p_Init(temp_id);
read[temp_id] = 1;
++faminum;//每次新录入一个人就要新增加一个家庭
}
int r = findR(temp_id);
cin >> p1 >> p2;
if (p1 != -1) {
if (!read[p1]) {
fami[p1].p_Init(p1);
read[p1] = 1;
++faminum;
}
unionF(r, p1);
}
if (p2 != -1) {
if (!read[p2]) {
fami[p2].p_Init(p2);
read[p2] = 1;
++faminum;
}
unionF(r, p2);
}
cin >> chil;
for (int j = 1; j <= chil; ++j)
{
int x; cin >> x;
if (!read[x]) {
fami[x].p_Init(x);
read[x] = 1;
++faminum;
}
unionF(r, x);
}
cin >> t_hnum >> t_hs;
fami[r].hnum += t_hnum;
fami[r].hs += t_hs;
}
int count = 0;
for (int i = 0; i < n; ++i) {
int r = findR(fir[i]);
if (!root[r]) {
root[r] = 1;
++count;
famiR.push_back(fami[r]);
}
if (count == faminum)
break;
}
sort(famiR.begin(), famiR.end());
cout << faminum << endl;
for (int i = 0; i < famiR.size(); ++i) {
if (i)
cout << endl;
cout <<setw(4)<<setfill('0')<<famiR[i].minid << " " << famiR[i].num << " "
<<setprecision(3)<<setiosflags(ios::fixed)<<famiR[i].hnum*1.0 / famiR[i].num << " "
<< famiR[i].hs *1.0/ famiR[i].num;
}
system("pause");
return 0;
}
网友评论