题目大意:求并查集中集合的个数,及每个集合的详细信息

解题关键:只要不进行unite,集合的根是不会变化的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
struct node{
int id,cnt,area;
}pe[];
struct nod{
int id,num,cnt,area;
double avcnt,avar;
}pa[];
bool vis[];
int par[];
int find1(int x){
if(x==par[x]) return x;
else return par[x]=find1(par[x]);
}
bool cmp(nod x,nod y){
if(x.avar==y.avar) return x.id<y.id;
else return x.avar>y.avar;
}
void unite(int x,int y){
x=find1(x);
y=find1(y);
if(x==y) return;
else par[x]=y;//为什么这里改变一下会有变化???
}
int main(){
int n;
scanf("%d",&n);
for(int i=;i<;i++){
par[i]=i;
}
for(int i=;i<n;i++){
int t1,t2,t3;
scanf("%d%d%d",&t1,&t2,&t3);
vis[t1]=true;
if(t2!=-){
unite(t1, t2);
vis[t2]=true;
}
if(t3!=-){
unite(t1,t3);
vis[t3]=true;
}
int k;
scanf("%d",&k);
for(int j=;j<k;j++){
int temp;
scanf("%d",&temp);
unite(t1,temp);
vis[temp]=true;
}
pe[i].id=t1;
int t4,t5;
scanf("%d%d",&t4,&t5);
pe[i].cnt=t4;
pe[i].area=t5;
} for(int i=;i<n;i++){
int id=find1(pe[i].id);
//id=find1(id);
pa[id].cnt+=pe[i].cnt;
pa[id].area+=pe[i].area;
// pa[id].num++;
} for(int i=;i<=;i++){//这里是核心
if(vis[i]){
//int t=par[i]=find1(i);
int t=find1(i);
if(!pa[t].num){
pa[t].id=i;
}
pa[t].num++;
pa[t].avar=pa[t].area*1.0/pa[t].num;//这里其实是重复覆盖的
pa[t].avcnt= pa[t].cnt*1.0/pa[t].num;
}
} sort(pa,pa+,cmp);
int ans=;
for(int i=;i<;i++){
if(pa[i].num){
ans++;
}
//else break;
}
printf("%d\n",ans);
for(int i=;i<ans;i++){
if(pa[i].num){
printf("%04d %d %.3lf %.3lf\n",pa[i].id,pa[i].num,pa[i].avcnt,pa[i].avar);
}
} }

最新文章

  1. 使用MonoTouch.Dialog简化iOS界面开发
  2. 引用类型的转换问题和instanceof
  3. 1、MVC和EF中的 Model First 和 Code First
  4. 使用页面Tag判断某个值为空值时,不能使用logic:equal(无效),可以使用logic:notPresent
  5. java 面向对象编程 --第十二章 JDK常用类
  6. 洛谷P1519 穿越栅栏 Overfencing
  7. 1.3查看Linux内核版本
  8. SQL Agent Job -&gt;&gt; 通过sys.sysprocesses的program_name字段来定位对应的Job
  9. 当里个当,免费的HTML5连载来了《HTML5网页开发实例详解》连载(一)
  10. W3C词汇和术语表
  11. HDOJ 1302(UVa 573) The Snail(蜗牛爬井)
  12. samba 开启
  13. Jmeter(四)-断言/检查点
  14. 02--Java TCP Socket编程
  15. 利用PYTHON设计计算器功能
  16. 机器翻译评测——BLEU改进后的NIST算法
  17. jquery slideDown 控制div出现的方向
  18. c#gridcontrol 的一些设置
  19. 提高 JavaScript 开发效率的高级 VSCode 扩展!
  20. vue.js插槽

热门文章

  1. 请求被中止: 未能创建 SSL/TLS 安全通道,以及解决方法,即:Could not create SSL/TLS secure channel
  2. hdu 2509 Be the Winner(anti nim)
  3. Linux系统调用分析
  4. java快捷键大全
  5. LeetCode OJ:Symmetric Tree(对称的树)
  6. hdu 4632 回文子序列计数
  7. 学习动态性能表(8)--v$lock&amp;v$locked_object
  8. 检测一个DLL文件是x64还是x86
  9. 一般处理程序+html 的CRUD
  10. VerilogHDL编译预处理