给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式：
输入第一行给出一个正整数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
简单并查集题目，就是看看一共有几个家族，设一个vis数组，访问过的全部标记为一，那么有亲子关系的就并到一起，f数组是并查集中记录每个点的父亲。
数据读取完了，把整个id范围读一遍，如果id和父亲点的id相同那么就记录他的地址。排个序，输出。
代码：
#include <stdio.h> #include <iostream> #include <algorithm> using namespace std ; #define MAX 10000///最大范围 int f[MAX],vis[MAX]={0};///f用于记录并查集每个点的父亲 vis记录是否访问过 struct family///家族结构体 { int id,people ; double area,house ;//area是占地面积 house是房产套数 }; family person[MAX],*ans[MAX];//person记录相应id的家族信息，ans是个指针数组，记录答案 int ant = 0;//ans数组下标 bool cmp(family *a,family *b)///排序比较函数 { if((a->area / a->people) == (b->area / b->people)) return a->id < b->id; return (a->area / a->people) > (b->area / b->people); } void init()///初始化f { for(int i = 0;i < MAX;i ++) f[i] = i; } int getf(int x)///get father { if(x != f[x])f[x] = getf(f[x]); return f[x]; } void marriage(int x , int y)///merge合并 { int xx,yy; xx = getf(x) ; yy = getf(y) ; if(xx != yy) { if(xx > yy)///方便找到最小id 让id小的当父亲那么找到的id与父亲相等的点最小id就是自己 { f[xx] = yy; } else f[yy] = xx; } } int main() { int n,id,mother,father,k,child; cin>>n; init(); for(int i = 0;i < n;i ++) { cin>>id>>father>>mother; vis[id] = 1 ; if(mother!=-1) {marriage(id,mother);vis[mother]=1;}///假如父亲访问过那么他肯定已经和id合并过 母亲也是 if(father!=-1) {marriage(id,father);vis[father]=1;} cin>>k; for(int j = 0;j < k;j ++) { cin>>child; if(child!=-1) { marriage(id,child); vis[child] = 1; } } cin>>person[id].house>>person[id].area;///id作为下标方便寻找 } for(int i = 0;i < MAX;i ++) { if(!vis[i])continue; int f = getf(i); if(f == i) { person[i].people ++; ans[ant ++] = &person[i]; person[i].id = i;///需要注明 continue; } person[f].people ++; person[f].house += person[i].house; person[f].area += person[i].area; } sort(ans,ans + ant,cmp); cout<<ant<<endl; for(int i = 0;i < ant;i ++) printf("%04d %d %.3f %.3f ",ans[i]->id,ans[i]->people,ans[i]->house/ans[i]->people,ans[i]->area/ans[i]->people); return 0 ; }
备赛重温：
#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <algorithm> using namespace std; int n; int f[10000],pnum[10000]; set<int> s; int id,fa,mo,k,child; double fn,fc,fnum[10000],fcover[10000]; void init() { for(int i = 0;i < 10000;i ++) { f[i] = i; pnum[i] = 1; } } int getf(int x) { return x == f[x] ? x : f[x] = getf(f[x]); } int mer_(int x,int y) { int xx = getf(x),yy = getf(y); if(xx != yy) { if(xx < yy) swap(xx,yy); pnum[yy] += pnum[xx]; fnum[yy] += fnum[xx]; fcover[yy] += fcover[xx]; f[xx] = yy; } return yy; } bool cmp(int a,int b) { if(fcover[a] == fcover[b]) return a < b; return fcover[a] > fcover[b]; } int main() { cin >> n; vector<int> ans; init(); for(int i = 0;i < n;i ++) { cin >> id >> fa >> mo >> k; s.insert(id); if(fa != -1) { s.insert(fa); id = mer_(id,fa); } if(mo != -1) { s.insert(mo); id = mer_(id,mo); } for(int j = 0;j < k;j ++) { cin >> child; s.insert(child); id = mer_(id,child); } cin >> fn >> fc; fnum[id] += fn; fcover[id] += fc; } for(set<int>::iterator it = s.begin();it != s.end();it ++) { if(f[*it] == *it) { fnum[*it] /= pnum[*it]; fcover[*it] /= pnum[*it]; ans.push_back(*it); } } sort(ans.begin(),ans.end(),cmp); cout << ans.size() << endl; for(vector<int>::iterator it = ans.begin();it != ans.end();it ++) { printf("%04d %d %.3f %.3f ",*it,pnum[*it],fnum[*it],fcover[*it]); } }