博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 3635 Dragon Balls(并查集技巧)
阅读量:7206 次
发布时间:2019-06-29

本文共 859 字,大约阅读时间需要 2 分钟。

题意:n个点m次询问,两种操作:1.将含有龙珠i的集合加入含有龙珠j的集合中;2.查询龙珠i所在堆的编号,龙珠个数,龙珠i的搬运次数;

思路:并查集,数组分别维护关系、数量、搬运次数;

#include
#include
#include
using namespace std;int n,m;int fa[500010],time[500010],num[500010];void init(){ for(int i=0;i<=n;i++) { fa[i]=i;num[i]=1;time[i]=0; }}int fin(int x){ if(fa[x]==x) return x; int j=fa[x]; fa[x]=fin(fa[x]); time[x]+=time[j];//累加搬移次数 return fa[x];}void combine(int a,int b){ int t1=fin(a); int t2=fin(b); if(t1!=t2) { fa[t1]=t2; num[t2]+=num[t1];//两个集合中的个数合并 time[t1]=1;//搬移次数置1 }}int main(){ char ch[5]; int i,j,k,t,a,b; scanf("%d",&t); for(j=1;j<=t;j++) { printf("Case %d:\n",j); scanf("%d%d",&n,&m); init(); for(i=0;i

 

转载于:https://www.cnblogs.com/dashuzhilin/p/4418866.html

你可能感兴趣的文章
jQuery的选择器(四)
查看>>
使用firefox和selenium模拟点击js获取更多评论
查看>>
SQL-mysql设置utf8编码方法
查看>>
5.4 异步TCP编程(三)
查看>>
采访Hadley Wickham
查看>>
iframe中的各种跳转方法
查看>>
oracle编程、操作不良习惯总结
查看>>
每天一个linux命令(26):用SecureCRT来上传和下载
查看>>
Oracle 表空间状态
查看>>
为redis分配一个新的端口
查看>>
利用Python做绝地科学家(外挂篇)
查看>>
费下载最新版万能视频格式转换器是一款功能强大的全能视频格式转换软件
查看>>
算法实战——多叉树全路径遍历
查看>>
MySQL数据类型和常用字段属性总结
查看>>
斑点检测(LoG,DoG)(下)
查看>>
《CLR Via C# 第3版》笔记之(二十二) - APM和EAP
查看>>
洛谷P5111 zhtobu3232的线段树
查看>>
Angular Cli 创建的Angular项目应用本地css文件和js文件
查看>>
java代码getHostAddress .getHostName()的练习
查看>>
【转】一个孩子关于MaD的思考概述
查看>>