hdu 3635 Dragon Balls(并查集应用)

时间:2022-03-08 15:43:28
Problem Description
Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together. 

hdu 3635 Dragon Balls(并查集应用)

His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities' dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls.
Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.
 
Input
The first line of the input is a single positive integer T( < T <= ).
For each case, the first line contains two integers: N and Q ( < N <= , < Q <= ).
Each of the following Q lines contains either a fact or a question as the follow format:
T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different.
Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). ( <= A, B <= N)
 
Output
For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space.
 
Sample Input

T
T
Q T
Q
T
Q
 
Sample Output
Case :
Case :
 
Author
possessor WC
 
Source
 
并查集,和前面的hdu2818很相似

主要是记录移动次数,其实每个根结点都是最多移动一次的,所以记录移动次数把自己的加上父亲结点的就是移动总数了

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stdlib.h>
using namespace std;
#define N 10006
int n,q;
int fa[N];
int mov[N];
int num[N];
void init(){
for(int i=;i<N;i++){
fa[i]=i;
num[i]=;
mov[i]=;
}
}
int find(int son){
if(fa[son]!=son){
int t=find(fa[son]);
mov[son]+=mov[fa[son]];
fa[son]=t;
}
return fa[son];
//return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
int root1=find(x);
int root2=find(y);
if(root1==root2)return;
fa[root1]=root2;
mov[root1]=;
num[root2]+=num[root1];
}
int main()
{
int ac=;
int t;
scanf("%d",&t);
while(t--){
init();
scanf("%d%d",&n,&q); char s[];
int x,y;
printf("Case %d:\n",++ac);
for(int i=;i<q;i++){
scanf("%s",s);
if(s[]=='T'){
scanf("%d%d",&x,&y);
merge(x,y);
}
else{
scanf("%d",&x);
int city=find(x);
printf("%d %d %d\n",city,num[city],mov[x]);
}
}
}
return ;
}

hdu 3635 Dragon Balls(并查集应用)的更多相关文章

  1. hdu 3635 Dragon Balls&lpar;并查集&rpar;

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  2. hdu 3635 Dragon Balls &lpar;带权并查集&rpar;

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  3. HDU 3635 Dragon Balls(超级经典的带权并查集!!!新手入门)

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  4. hdu 3635 Dragon Balls(加权并查集)2010 ACM-ICPC Multi-University Training Contest(19)

    这道题说,在很久很久以前,有一个故事.故事的名字叫龙珠.后来,龙珠不知道出了什么问题,从7个变成了n个. 在悟空所在的国家里有n个城市,每个城市有1个龙珠,第i个城市有第i个龙珠. 然后,每经过一段时 ...

  5. hdu 3635 Dragon Balls &lpar;MFSet&rpar;

    Problem - 3635 切切水题,并查集. 记录当前根树的结点个数,记录每个结点相对根结点的转移次数.1y~ 代码如下: #include <cstdio> #include &lt ...

  6. hdu 3635 Dragon Balls

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Tot ...

  7. HDU 3635 Dragon Balls(带权并查集)

    http://acm.hdu.edu.cn/showproblem.php?pid=3635 题意: 有n颗龙珠和n座城市,一开始第i颗龙珠就位于第i座城市,现在有2种操作,第一种操作是将x龙珠所在城 ...

  8. hdu 3635 Dragon Balls(并查集)

    题意: N个城市,每个城市有一个龙珠. 两个操作: 1.T A B:A城市的所有龙珠转移到B城市. 2.Q A:输出第A颗龙珠所在的城市,这个城市里所有的龙珠个数,第A颗龙珠总共到目前为止被转移了多少 ...

  9. HDU 1811 拓扑排序 并查集

    有n个成绩,给出m个分数间的相对大小关系,问是否合法,矛盾,不完全,其中即矛盾即不完全输出矛盾的. 相对大小的关系可以看成是一个指向的条件,如此一来很容易想到拓扑模型进行拓扑排序,每次检查当前入度为0 ...

随机推荐

  1. MSSQL数据库索引的应用

    一.索引的概念 索引就是加快检索表中数据的方法.数据库的索引类似于书籍的索引.在书籍中,索引允许用户不必翻阅完整个书就能迅速地找到所需要的信息.在数据库中,索引也允许数据库程序迅速地找到表中的数据,而 ...

  2. Uva 10537 过路费

    题目链接:http://vjudge.net/contest/143062#problem/C 题意: 给定一个无向图,大写字母是城市,小写字母是村庄,经过城市交过路费为当前货物的%5,路过村庄固定交 ...

  3. 如何防止ElasticSearch集群出现脑裂现象(转)

    原文:http://xingxiudong.com/2015/01/05/resolve-elasticsearch-split-brain/ 什么是“脑裂”现象? 由于某些节点的失效,部分节点的网络 ...

  4. hdu 4452

    今天模拟赛的一个模拟题: 每次看到这种题就感觉很繁琐: 这次静下心来写写,感觉还不错!就是很多错误,浪费了一点时间: 代码: #include<cstdio> #include<cs ...

  5. commonjs模块和es6模块的区别

    commonjs模块与es6模块的区别 到目前为止,已经实习了3个月的时间了.最近在面试,在面试题里面有题目涉及到模块循环加载的知识.趁着这个机会,将commonjs模块与es6模块之间一些重要的的区 ...

  6. Red Hat Enterprise 7&period;5 安装后无法进入图形界面 This system is not registered with an entitlement server&period; You can use subscription-manager to register&period;

    This system is not registered with an entitlement server. You can use subscription-manager to regist ...

  7. docker zabbix

    1.zabbix-mysql 数据库 sudo docker pull zabbix/zabbix-server-mysql sudo docker run --name some-zabbix-se ...

  8. 产品排序&lpar;2015 年北大自招夏令营&rpar; (与栈相关的区间DP)

    题面: \(solution:\) 又是一道\(DP\)的好题啊!状态并不明显,需要仔细分析,而且还结合了栈的特性! 做这一类题,只要出题人有点理想,一定会在栈的性质上做点文章,所以我们尽量围绕栈的性 ...

  9. SharePoint &lowbar;layouts下自定义程序页面权限管理

    在sharepoint中,_layouts下的自定义页面没有特别的权限,只要用户能访问sharepoint站点就可以访问_layouts下的自定义程序页面,现在我们需要给自定义页面做一下权限认证.要求 ...

  10. Linux之解决命令行cat命令中文乱码

    临时解决cat中文乱码 cat test.txt | iconv -f GBK -t UTF-8