LA3027简单带权并查集
题意:
有n个点,一开始大家都是独立的点,然后给出一些关系,a,b表示a是b的父亲节点,距离是abs(a-b)%1000,然后有一些询问,每次询问一个节点a到父亲节点的距离是多少?
思路:
可以直接简单带权并查集就能搞定,核心代码是这样,设s_x[i]表示i到自己父亲节点的距离,然后
//处理并查集的时候
int finds(int x)
{
if(x == mer[x]) return x;
int k = mer[x];
mer[x] = finds(mer[x]);
mer[x] += mer[k];
return mer[x];
}
//建立关系的时候
mer[a] = b;
s_x[a] = abs(a - b) % 1000
//询问的时候
x = finds(a);//这一部别忘记了,因为并查集用了路径压缩,查询一次之后才能更新到他到根的距离,不然后可能只是他到他上一个节点的距离,查询后经过路径压缩会把他上一个节点变成他的根节点。
printf(s_x[a]);
#include<stdio.h>
#include<string.h>
#define N 22000
int mer[N] ,s_x[N];
int abss(int x)
{
return x > 0 ? x : -x;
}
int finds(int x)
{
if(x == mer[x]) return x;
int k = mer[x];
mer[x] = finds(mer[x]);
s_x[x] =(s_x[x] + s_x[k]);
return mer[x];
}
int main ()
{
int t ,n ,a ,b;
char str[5];
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
for(int i = 0 ;i <= n ;i ++)
mer[i] = i ,s_x[i] = 0;
while(~scanf("%s" ,str) && str[0] != 'O')
{
if(str[0] == 'I')
{
scanf("%d %d" ,&a ,&b);
mer[a] = b;
s_x[a] = abss(a - b) % 1000;
}
else
{
scanf("%d" ,&a);
finds(a);
printf("%d\n" ,s_x[a]);
}
}
}
return 0;
}
最新文章
- Spring 在多线程中,bean的注入问题
- ie浏览器 jsp中链接参数为中文的处理
- PHP foreach使用
- [stm32] MPU6050 HMC5883 Kalman 融合算法移植
- 适用于jquery1.11.1的ajaxfileupload.js
- [HDOJ3308]LCIS(线段树,区间合并)
- SqlServer 之 查看表空间
- 多线程程序设计学习(13)Active Object pattern
- hdu 1043 pku poj 1077 Eight (BFS + 康拓展开)
- html结构,第一节
- javascript面向对象程序设计系列(一)---创建对象
- Linux如何查找文件安装路径?
- Oracle存储过程的调用和执行
- (1-1)SpringCloud-Eureka:服务的注册与发现
- mysql修改记录
- Dubbo 支持哪些序列化协议?
- 在java中写出完美的单例模式
- 几何学观止(Riemann流形部分)
- 【spring基础】spring声明式事务详解
- Codeforces 36B - Fractal
热门文章
- EurekaServer源码分析
- java 流程控制学习
- 还在用crontab? 分布式定时任务了解一下
- java异常的 理解
- BZOJ_2115 [Wc2011] Xor 【图上线性基】
- 二叉树的建立与遍历(c语言)入门
- P1996_约瑟夫问题(JAVA语言)_可能是最简单的解法了!
- ch2_8_4求解投骰子游戏问题
- Python基础之数据类型详解
- PAT (Basic Level) Practice (中文)1070 结绳 (25 分) 凌宸1642