用并查集处理每个家庭的信息,注意标记~

#include<bits/stdc++.h>
using namespace std;
const int maxn=;
bool visit[maxn]={false};
int N;
struct node {
int id;
int child[];
double num;
double area;
}Node[maxn];
struct family {
int id;
double num;
double area;
int renshu;
}f[maxn];
int father[maxn];
void init () {
for (int i=;i<maxn;i++)
father[i]=i;
}
int findfather (int x) {
int a=x;
while (x!=father[x])
x=father[x];
while (a!=father[a]) {
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
void Union (int a,int b) {
int faA=findfather (a);
int faB=findfather (b);
if (faA<faB) father[faB]=faA;
else father[faA]=faB;
};
bool cmp (family a,family b) {
if (a.area!=b.area) return a.area>b.area;
else return a.id<b.id;
}
int main () {
scanf ("%d",&N);
int id,fatherid,motherid,k;
double num,area;
init ();
for (int i=;i<N;i++) {
scanf ("%d %d %d %d",&id,&fatherid,&motherid,&k);
Node[i].id=id;
visit[id]=true;
if (fatherid!=-) {
visit[fatherid]=true;
Union (id,fatherid);
}
if (motherid!=-) {
visit[motherid]=true;
Union (id,motherid);
}
for (int j=;j<k;j++) {
scanf ("%d",&Node[i].child[j]);
visit[Node[i].child[j]]=true;
Union (id,Node[i].child[j]);
}
scanf ("%lf %lf",&Node[i].num,&Node[i].area);
}
for (int i=;i<N;i++) {
f[findfather(Node[i].id)].area+=Node[i].area;
f[findfather(Node[i].id)].num+=Node[i].num;
}
int ans=;
for (int i=;i<maxn;i++) {
if (visit[i]==true) {
f[findfather(i)].renshu++;
f[findfather(i)].id=findfather(i);
}
}
for (int i=;i<maxn;i++)
if (f[i].renshu!=) {
ans++;
f[i].area/=f[i].renshu;
f[i].num/=f[i].renshu;
}
sort (f,f+maxn,cmp);
printf ("%d\n",ans);
for (int i=;i<ans;i++) {
printf ("%04d %d %.3f %.3f\n",f[i].id,f[i].renshu,f[i].num,f[i].area);
}
return ;
}

最新文章

  1. const int *
  2. 图解Android - Looper, Handler 和 MessageQueue
  3. DrawText
  4. android开发事件监听
  5. SQL Server 基础:Join用法
  6. (第二章)Java并发机制的底层实现原理
  7. iOS 面试题汇总
  8. 搭建firefly服务端遇到的问题
  9. rowid去重(删除表的重复记录)
  10. C语言之基本算法37—数组最大值及其位置
  11. metamask源码学习-background.js
  12. SaltStack 模块
  13. day08-字符串操作
  14. java实现点选汉字验证码
  15. 【JAVA】异常笔记
  16. JAVA-JSP动作元素之param
  17. 20145311 《Java程序设计》第十周学习总结
  18. Eclipse设置Courier New字体
  19. gradle 刷新缓存
  20. 高性能缓存服务器Varnish

热门文章

  1. innerHTML,innerText,textContent
  2. JVM工具使用和Linux-top命令解析
  3. yii2 password hash生成与验证方法
  4. 最全的 eclipse web 项目目录结构以及Tomcat的各个目录的作用
  5. C语言笔记 10_文件读写&amp;预处理器
  6. vue项目用npm安装sass包遇到的问题及解决办法
  7. MAC记住 git的用户名密码
  8. 事件和方法的区别,以input框的blur事件为例
  9. lintcode算法周竞赛
  10. 《如何增加资本约见》---创业学习---训练营第四课---HHR---