当前位置：首页 > 编程日记 > 正文

【HDU】3635 Dragon Balls （带权并查集一）

编程日记 2024-10-14 00:10:00

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3635

【问题描述】

有标号为1到n的n个龙珠，分别放在对应标号为1到n的n个城市里。
下面有两种操作:
T A B表示把A龙珠所在城市的所有龙珠都转移到B龙珠所在的城市中
Q A 表示查询A，需要知道A龙珠现在所在的城市，A所在的城市有几颗龙珠，A转移到这个城市移动了多少次,分别输出3个整数，表示上述信息。

【输入描述】

第一行一个整数T表示测试数据组数T∈[0,100]
对于每一组测试数据，第一行包含两个整数N,Q∈[2,10000]
接下来Q行，每行包含如下的操作或询问：T A B或Q A，如题目描述所示。

【输出描述】

对于每一组测试数据，先输出一行Case x:(x表示测试数据标号，从1开始)，然后对于每一个询问，输出一行三个数表示答案，用空格隔开

【样例输入】

【样例输出】

Case 1:
2 3 0
Case 2:
2 2 1 
3 3 2

开三个数组

pre数组：pre[i]表示第i个球所在的城市

sum数组：sum[i]表示第i个城市所拥有的球的个数

cnt数组：cnt[i]表示第i个球移动了几次

init()：初始化，每一个球原来都呆在自己的城市，所以每一个城市里都只有1个球，每一个球的移动次数都是0。

如果输入的是T，x，y，则find函数找到x和y的根结点，在find函数递归的时候，先是一直延伸向下，找到它的根结点fx，然后在回溯的过程中修改cnt数组（即cnt[i]表示第i个球移动的次数）以及进行压缩路径。

某一个球移动的次数 = 他自己移动的次数 + 它上面的根结点移动的次数，所以find(pre[x])一直延伸向上找到最高的那一个点，然后再回溯的过程中加上每一个根结点移动的次数，逐个加上，涉及到的点都要进行路径压缩，把相应的点连接到fx上

举个例子：

一组测试数据：

第一步：

sum[1] = 1 cnt[1] = 0 pre[1]=1

sum[2] = 1 cnt[2] = 0 pre[2]=2

sum[3] = 1 cnt[3] = 0 pre[3]=3

第二步

在join函数中，find函数没有进行递归，直接返回，fx=1，fy=2，1连到2上，fx（就是x，也就是1）为根结点，移动次数被置为1，pre[1] = 2

第三步：

再次连接的时候，y=3，在调用find函数的时候，直接返回fy=3。但是，x=2，是先一直递归得到fx=2，回溯，退回到x=1，pre[1]=2，cnt[1] += cnt[2]，这时候的cnt[2]=0，路径压缩，pre[1]=2，返回2给fx。之后pre[2] =3（得到的状态如上面那幅图所示，将1的根结点连接到3，用题目中的话来说就是将1所在的城市的所有龙珠转移到3城市中，所以3所在的城市的龙珠数量要加上1所在的城市的龙珠的数量，这是1和2在一个城市，之后因为都移走了，所以要置0），sum[3]+=sum[2]，sum[2]=0。移动的那个根结点cnt的值置为1。

第四步：

在主函数中，假设要查找的结点是a，root来接受find(a)的值，在调用find函数的同时会进行路径压缩，图的状态会变成上面那种样子，先是x=3，直接返回3给fx，这是x=2了，cnt[2]+=cnt[3]（cnt[3]=0，因为没有移动过），pre[2]=3，在返回3给fx，这时候x=1，cnt[1]+=cnt[2]，所以cnt[1]变成了2，pre[1]=3，（fx一直接受的返回值都是3），所以，1也连接到3上去了。在最后的输出中，注意保存要查找的根结点就好，前两个输出的数都是要按照根结点来找的，最后一个是根据结点的序号去找的。

只要递归遍历到的点，都会直连到该集合的根节点下，如果遍历到的点还有子树，但是子树上的结点不涉及在这一次递归中，那么就直接一整棵子树连接到该集合的根节点上去。

在回退的过程中，一开始找到的fx（即那个集合的根结点）一直保存在fx中，就是为了pre[x]=fx。

例如要创建的是这样的一棵树，为了看出路径压缩的过程，我们在输入数据的时候，要从下网上输入。

Q 1

还是这一种状态，pre[1] = 1，之前都是其他的点的移动，最后是连接到1上，1没有移动过

Q 3

在递归的过程中，3，2，1，接着回溯，所以这三个点，最后都会路径压缩，直接连接到1上，像2和3还连接着其他子树，就直接一起，以2和3为根一起带过去了。

之后再Q 3 ，也不会发生改变了，因为已经路径压缩完成，是当前的最优状态了。

之后再试一下Q 4

（现在大家可以体会到递归以及路径压缩是怎么一回事了吗）

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;const int maxn = 10005;int pre[maxn];
int sum[maxn];
int cnt[maxn];
int n,m,root;
char str[3];void init()
{for(int i=0;i<maxn;i++){pre[i] = i;sum[i] = 1;cnt[i] = 0;}
}int find(int x)
{if(x==pre[x])return x;int fx = find(pre[x]);cnt[x] += cnt[pre[x]];pre[x] = fx;return fx;
}void join(int x,int y)
{int fx = find(x);int fy = find(y);if(fy==fx)return ;pre[fx] = fy;sum[fy] += sum[fx];sum[fx] = 0;cnt[fx] = 1;
}int main ()
{int T,k=1,i;int x,y,a;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);printf("Case %d:\n",k++);init();while(m--){scanf("%s",str);if(str[0]=='T'){scanf("%d%d",&x,&y);join(x,y);}else if(str[0]=='Q'){scanf("%d",&a);root = find(a);/*for(i=1;i<=n;i++){printf("pre[%d]=%d\n",i,pre[i]); }*/printf("%d %d %d\n",root,sum[root],cnt[a]);}/*for(i=1;i<=n;i++){cout << "sum["<<i<<"] = " << sum[i] << ",pre["<<i << "] = "<<pre[i] << ",cnt["<<i<<"] = " << cnt[i]<< endl;}*/}}return 0;
}

https://www.dkcj.cn/info/22930.html

【HDU】3635 Dragon Balls （带权并查集一）

相关文章：

php源码安全加密之PHP混淆算法.

Element 2.6.0 发布，基于 Vue 2.0 的桌面端组件库

【Python】随机函数

IOS/Android模拟器运行APP调试方法

python数据结构与算法：单向链表

Vue性能优化：如何实现延迟加载和代码拆分？

GitHub怎样fork别人代码到自己仓库并进行贡献

python数据结构与算法：单向循环列表

http权威指南-http连接管理

在macos上基于python2.7安装PyQt5

python数据结构与算法：二分查找

使用maven镜像

Jupyter Notebook 快捷键（基本）

关于二叉树的几个必须掌握的实现

python数据结构与算法：队列与双端队列

view5.3登录桌面提示当前可用桌面资源不足

【HDU】4706 Children's Day（模拟）

详解原生AJAX请求demo（兼容IE5/6）

【POJ】3268 Silver Cow Party （将有向图的边反转）

项目管理深入理解08--成本管理

python数据结构与算法：双向链表

如何开发一个区块链应用程序

python数据结构与算法：栈

【PAT (Basic Level) 】1014 福尔摩斯的约会 (20 分)

菜鸟物流云是如何帮助快递合作伙伴解决双11巨大业务负荷的？

安装H3C的各种问题

前景背景分割——ostu算法的原理及实现 OpenCV (八）

【PAT (Basic Level) 】1015 德才论 (25 分)

浏览器启动外部软件

Luogu P1082 同余方程(NOIP 2012) 题解报告