PTA天梯赛L2-007家庭房产题解：用C++并查集+结构体搞定复杂家庭关系统计（附完整代码）

PTA天梯赛L2-007家庭房产题解C并查集与结构体的高效应用在算法竞赛中处理复杂关系网络是常见挑战。PTA天梯赛L2-007家庭房产题目正是这类问题的典型代表要求选手统计每个家庭的人口、房产套数和人均面积。这道题看似简单实则暗藏多个技术要点包括并查集的优化使用、结构体的灵活设计以及边界条件的处理。本文将深入剖析解题思路提供可直接用于竞赛的代码实现并分享实战中容易忽略的关键细节。1. 问题分析与数据结构选择面对家庭关系网络我们需要选择能够高效处理动态连通性的数据结构。并查集Disjoint Set Union以其接近常数时间的合并与查询复杂度成为首选。题目中的每个家庭本质上是一个连通分量而并查集的核心功能正是管理元素的动态分组关系。关键数据结构设计const int N 1e5; struct Node { int id, cnt; // 最小编号、家庭人口数 double House, S; // 总房产套数、总面积 } node[N]; int p[N]; // 并查集父节点数组 bool vis[N]; // 标记存在的编号这个设计巧妙地将并查集与统计信息分离p[]数组维护纯粹的父子关系node[]结构体数组存储每个家庭的聚合数据vis[]数组标记实际存在的成员编号2. 并查集实现与优化技巧标准并查集需要两个基本操作查找根节点和合并集合。本题的特殊之处在于要求以最小编号作为家庭代表这直接影响合并策略。路径压缩与最小编号维护int find(int x) { if (p[x] ! x) p[x] find(p[x]); return p[x]; } void merge(int a, int b) { a find(a), b find(b); if (a b) p[a] b; // 始终将较大编号合并到小编号下 else p[b] a; }这种实现方式确保了路径压缩优化查询效率合并时自动维护最小编号为根节点避免重复计算和无效合并注意初始化时需遍历整个编号范围0-9999设置p[i]i这是处理0000等特殊编号的前提。3. 输入处理与数据聚合题目输入包含复杂的亲属关系网络需要分层次处理父母、子女等不同关系类型。每行输入的处理流程如下读取本人编号和父母信息若父母存在分别与本人合并读取所有子女并合并关系记录房产信息到当前集合的根节点关键处理代码while (n--) { int id, fa, mo; cin id fa mo; vis[id] 1; if (fa ! -1) { merge(id, fa); vis[fa] 1; } if (mo ! -1) { merge(id, mo); vis[mo] 1; } // 处理子女... double house, s; cin house s; id find(id); node[id] {id, 0, node[id].House house, node[id].S s}; }这种延迟聚合策略先将房产信息加到当前根节点最后统一计算家庭人数避免了在合并过程中频繁更新统计信息。4. 统计计算与结果输出在所有关系处理完成后需要遍历所有存在的编号统计各家庭实际人数收集所有有效的家庭根节点计算人均房产指标按要求排序输出统计与排序实现for (int i 0; i N; i) { if (vis[i]) { node[find(i)].cnt; if (find(i) ! i) { // 避免重复累加 node[find(i)].House node[i].House; node[find(i)].S node[i].S; } } } vectorNode res; for (int i 0; i N; i) { if (vis[i] p[i] i) { // 是根节点且存在 res.push_back({i, node[i].cnt, node[i].House / node[i].cnt, node[i].S / node[i].cnt}); } } sort(res.begin(), res.end(), [](Node a, Node b) { return a.S ! b.S ? a.S b.S : a.id b.id; });输出时需特别注意编号的格式化输出如0001需要保持四位printf(%04d %d %.3lf %.3lf\n, t.id, t.cnt, t.House, t.S);5. 常见错误与调试技巧在实际竞赛中这道题有几个典型陷阱编号0000的处理许多选手初始化时忽略0导致这个特殊编号无法正确处理房产信息重复计算在合并家庭时如果没有正确设计聚合逻辑可能导致房产数据被多次计算输出格式错误人均值需要保留3位小数编号需要保持4位输出调试建议使用小规模测试数据验证边界情况打印中间结果检查合并是否正确单独测试排序函数是否符合题目要求6. 性能优化与扩展思考虽然题目给出的N≤1000看似不大但编号范围可能达到10000。我们的实现已经考虑了这些因素并查集带有路径压缩实际效率接近O(α(N))统计阶段只需遍历存在的编号通过vis数组优化输出前用vector存储结果避免不必要的排序开销对于更大规模的数据如N≤1e5可以考虑使用哈希表记录存在的编号替代vis数组遍历在合并时即时更新统计信息减少后期处理采用更高效的内存管理策略在实际项目中处理类似家庭关系数据时可能需要考虑动态增加家庭成员处理离婚、再婚等复杂关系变化支持更丰富的查询类型如任意两人的关系判断7. 完整代码实现与注释以下是整合所有优化后的完整解决方案关键位置添加详细注释#include bits/stdc.h using namespace std; const int N 1e5; // 覆盖所有可能的4位编号 struct Node { int id, cnt; // 最小编号家庭人数 double House, S; // 人均套数人均面积 } node[N]; int p[N]; // 并查集父节点 bool vis[N]; // 标记存在的编号 // 路径压缩查找 int find(int x) { if (p[x] ! x) p[x] find(p[x]); return p[x]; } // 合并集合始终维护最小编号为根 void merge(int a, int b) { a find(a), b find(b); if (a b) p[a] b; else p[b] a; } int main() { // 初始化并查集 for (int i 0; i N; i) p[i] i; int n; cin n; while (n--) { int id, fa, mo, k; cin id fa mo k; vis[id] true; // 合并父母关系 if (fa ! -1) { merge(id, fa); vis[fa] true; } if (mo ! -1) { merge(id, mo); vis[mo] true; } // 合并子女关系 while (k--) { int child; cin child; merge(id, child); vis[child] true; } // 累加房产到根节点 double house, area; cin house area; int root find(id); node[root].House house; node[root].S area; } // 统计各家庭实际人数 for (int i 0; i N; i) { if (vis[i]) { int root find(i); node[root].cnt; // 累加非根节点的房产信息 if (root ! i) { node[root].House node[i].House; node[root].S node[i].S; } } } // 收集有效家庭 vectorNode families; for (int i 0; i N; i) { if (vis[i] p[i] i) { // 是根且存在 families.push_back({ i, node[i].cnt, node[i].House / node[i].cnt, node[i].S / node[i].cnt }); } } // 按要求排序 sort(families.begin(), families.end(), [](const Node a, const Node b) { return a.S ! b.S ? a.S b.S : a.id b.id; }); // 输出结果 cout families.size() endl; for (auto f : families) { printf(%04d %d %.3lf %.3lf\n, f.id, f.cnt, f.House, f.S); } return 0; }这段代码已经过PTA平台测试能够正确处理所有测试用例包括包含0000编号的特殊情况。在竞赛中建议将常用代码片段如并查集实现提前准备好作为模板可以节省宝贵的编码时间。