思路:
信息读入,每个家庭成员连一条边。
将一个家庭的合并到一个集合,且维护根节点是最小编号。
同时更新整个家庭的房产数量和房产面积。
找出每个根节点,排序输出相应信息
注意:
1. id是4位数字,遍历时有些id并未出现,所以要有个数组记录出现过的id
2. 输出时id不足4位需前补0
3. 更新信息的时候,只需更新根节点的信息就行了
c++代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n;
int p[N];
int c[N], hc[N], ha[N];
bool st[N];
struct Edge{
int a, b;
}e[N];
struct Family {
int id, c, s, a;
bool operator< (const Family &t) const {
if (a * t.c != t.a * c) return a * t.c > t.a * c;
return id < t.id;
}
};
int find(int x) {
if (x != p[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;
st[id] = true; //这里不能省略, 可能有人没有其他家人
if (~father) e[m++] = {id, father};
if (~mother) e[m++] = {id, mother};
for (int j = 0; j < k; j++) {
int t;
cin >> t;
e[m++] = {id, t};
}
cin >> hc[id] >> ha[id];
}
for (int i = 0; i < N; i++) p[i] = i, c[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);
if (pa != pb) {
if (pa < pb) swap(pa, pb);
p[pa] = pb;
c[pb] += c[pa];
hc[pb] += hc[pa];
ha[pb] += ha[pa];
}
}
vector<Family> res;
for (int i = 0; i < N; i++)
if (st[i] && p[i] == i)
res.push_back({i, c[i], hc[i], ha[i]});
sort(res.begin(), res.end());
cout << res.size() << '\n';
for (auto t : res)
printf("%04d %d %.3f %.3f\n",t.id, t.c, (double)t.s / t.c, (double)t.a / t.c);
return 0;
}