建图+DFS
题解
在热身赛的时候没有做出来，用的并查集的思想，但是敲残了，最后也没整出来。赛后听到别人的解题思路，感觉挺有收获的。利用每个人的关系可以建立一个无向图，最后用DFS遍历这个图，就能知道有几个连通分量，即家庭的数目。
当一个解题思想耗费差不多一个小时还没敲出来，可能你的大致思想确实可以将这个题目解出来，但是你目前的状态还不能很好的解决这个问题。例如这个题，一看题目就知道这个是跟并查集有关的，然后就一头扎进去，到最后也没有解出来，虽然确实可以用并查集解决这个题目。
这个时候我们应该多想想看，能否将这个题目转化成另外一种思想从而能够更好的解决，有意识的训练自己的发散思维，在平时的练习中对一个题目进行一题多解。
代码如下：
#include#include #include #include #include #include using namespace std;const int maxn = 10000;const int inf = 0x3f3f3f3f;bool vis[maxn];double house[maxn],area[maxn];vector v[maxn];int n, min_id, cnt;double sum_house, sum_area;struct Node { int id, sum_person; double avg_house, avg_area; Node(){} Node(int a, int b, double c, double d) { id = a; sum_person = b; avg_house = c; avg_area = d; }};vector ans;bool cmp(Node A, Node B) { if(A.avg_area != B.avg_area) return A.avg_area > B.avg_area; else return A.id < B.id;}void dfs(int x) { vis[x] = false; min_id = min(min_id, x); cnt++; sum_house += house[x]; sum_area += area[x]; int len = v[x].size(); for(int i = 0; i < len; i++) { if(vis[v[x][i]]) { dfs(v[x][i]); } }}int main() { scanf("%d", &n); memset(vis, 0, sizeof(vis)); for(int i = 0; i < maxn; i++) v[i].clear(); int id, fa, mo, num, kid; for(int i = 0; i < n; i++) { scanf("%d%d%d%d", &id, &fa, &mo, &num); vis[id] = true; if(fa != -1) { v[id].push_back(fa); v[fa].push_back(id); vis[fa] = true; } if(mo != -1) { v[id].push_back(mo); v[mo].push_back(id); vis[mo] = true; } for(int j = 0; j < num; j++) { scanf("%d", &kid); v[id].push_back(kid); v[kid].push_back(id); vis[kid] = true; } scanf("%lf%lf", &house[id], &area[id]); } ans.clear(); int kase = 0; for(int i = 0; i < maxn; i++) { if(vis[i]) { kase++; min_id = inf; cnt = 0; sum_house = sum_area = 0; dfs(i); Node node = Node(min_id, cnt, sum_house/cnt, sum_area/cnt); ans.push_back(node); } } sort(ans.begin(), ans.end(), cmp); printf("%d\n", kase); int len = ans.size(); for(int i = 0; i < len; i++) { printf("%04d %d %.3lf %.3lf\n", ans[i].id, ans[i].sum_person, ans[i].avg_house, ans[i].avg_area); } return 0;}