题目链接：点击打开链接
题目大意：略。
解题思路：并查集 + STL 大杂烩。注意：并查集中，不能参与统计操作，因为会出现中途连接之前断开的结点，这样之前的计算就会有误差。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; const int maxn=1e4+10; int pre[maxn], area[maxn], cnt[maxn]; set<int> hst, st[maxn]; set<int>::iterator sit; unordered_map<int,int> ump; unordered_map<int,int>::iterator it; struct peo { int id, num; double cnt, area; }ps[maxn]; void init() { for(int i=0;i<maxn;i++) pre[i]=i; } int findx(int x) { return pre[x]==x ? x : pre[x]=findx(pre[x]) ; } void join(int x,int y) { int fx=findx(x), fy=findx(y); if(fx!=fy) pre[fx]=fy; } int cmp(peo p1,peo p2) { if(p1.area==p2.area) return p1.id<p2.id; return p1.area>p2.area; } int main() { init(); int n,id,pid1,pid2,k,tid,a,b,oid; scanf("%d",&n); // 只处理并查集操作，+-操作不能放在这区域，因为可能会出现两个一开始毫无关联，但中途把之前两个关联起来，这样就会有误算 for(int i=0;i<n;i++) { scanf("%d%d%d%d",&id,&pid1,&pid2,&k); oid=id; // 为下面保存 cnt area 用的 id=findx(id); ump[id]=1; if(pid1!=-1) join(pid1,id), ump[pid1]=1; if(pid2!=-1) join(pid2,id), ump[pid2]=1; while(k--) scanf("%d",&tid), join(tid,id), ump[tid]=1; scanf("%d%d",&a,&b); cnt[oid]=a; area[oid]=b; } for(it=ump.begin(); it!=ump.end(); it++) { id=findx(it->first); st[id].insert(it->first); // 利用 key 自动排序，筛选编号最小 hst.insert(id); // 收集每个家庭的祖先结点 if(id!=it->first) cnt[id]+=cnt[it->first], area[id]+=area[it->first]; } int l=0; for(sit=hst.begin();sit!=hst.end();sit++) { ps[l].id=*(st[*sit].begin()); ps[l].num=st[*sit].size(); ps[l].cnt=cnt[*sit]*1.0/ps[l].num; ps[l].area=area[*sit]*1.0/ps[l].num; l++; } sort(ps,ps+l,cmp); printf("%d\n",l); for(int i=0;i<l;i++) printf("%04d %d %.3f %.3f\n",ps[i].id,ps[i].num,ps[i].cnt,ps[i].area); return 0; }
