天梯题集——家庭房产（并查集）

天梯题集——家庭房产（并查集）"/>

天梯题集——家庭房产（并查集）

家庭房产

解题步骤

①、并查集
将每个家庭都看成一个集合，再统计每个家庭的人数、房产套数、总面积。
②、计算有效数据
对于每个家庭来说
人均房产套数：房产套数/家庭人数
人均房产面积：总面积/家庭人数
③、排名
利用 sort() 函数得出排名。

实现代码

#include<bits/stdc++.h>
using namespace std;
int u[10010], C[10010], S[10010];
bool judge[10010]={false};
struct node{int sum_c;int sum_s;int min_bh;int men;double pj_s;double pj_c;
}f[10010];int get_(int x){if(u[x]==x) return x;return u[x]=get_(u[x]);
}bool cmp1(node a, node b){return a.sum_c>b.sum_c;
}bool cmp2(node a, node b){if(a.pj_s==b.pj_s)return a.min_bh<b.min_bh;return a.pj_s>b.pj_s;
}int main(){int n;memset(C, 0, sizeof(C));memset(S, 0, sizeof(S));for(int i=0; i<=10000; i++){u[i] = i;f[i].min_bh = 10010;f[i].men = 0;}scanf("%d", &n);while(n--){int num, fa, mu;scanf("%d%d%d", &num, &fa, &mu);judge[num]=true;if(fa!=-1){judge[fa]=true;int x = get_(num);u[x] = get_(fa);}if(mu!=-1){judge[mu]=true;int x = get_(num);u[x] = get_(mu);}int k;scanf("%d", &k);for(int i=0; i<k; i++){int child;scanf("%d", &child);judge[child]=true;int x = get_(child);u[x] = get_(num);}scanf("%d%d", &C[num], &S[num]);}int c=0;for(int i=0; i<=10000; i++){if(judge[i]){if(u[i]==i) c++;else u[i] = get_(i);f[u[i]].sum_c += C[i];f[u[i]].sum_s += S[i];f[u[i]].min_bh = min(i, f[u[i]].min_bh);f[u[i]].men++;}}//将有效的数据置前sort(f, f+10010, cmp1);for(int i=0; i<c; i++){f[i].pj_c = (double)f[i].sum_c/f[i].men;f[i].pj_s = (double)f[i].sum_s/f[i].men;}sort(f, f+c, cmp2);printf("%d\n", c);for(int i=0; i<c; i++){printf("%04d %d %.3lf %.3lf\n", f[i].min_bh, f[i].men,f[i].pj_c, f[i].pj_s);}return 0;
}