hdu 3635 Dragon Balls(并查集)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hdu 3635 Dragon Balls(并查集),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3937字,纯文字阅读大概需要6分钟。
内容图文
Dragon Balls
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2909 Accepted Submission(s): 1125
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.
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(0 < T <= 100).
For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000).
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). (1 <= 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
2 3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1
Sample Output
Case 1: 2 3 0 Case 2: 2 2 1 3 3 2
::挺不错的一道题,并查集,个人觉得维护某个球移动次数最难想到怎么去维护。
对于一个点的移动次数只要在合并的时候把该点移动次数加上其父亲的移动次数就好了。(想想,只有移动次数为0的球才能作为一个集合的“根”);
下面的代码思想是一样的,只是后一种用了点小技巧,省空间
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5usingnamespace std; 6constint N = 10010; 7int _, cas=1, n, m, fa[N], num[N], shift[N]; 8 9void init() 10{ 11for(int i=1; i<=n; i++) fa[i]=i, num[i]=1, shift[i]=0; 12} 1314int find(int x) 15{ 16if(x==fa[x]) return x; 17int p = fa[x]; 18 fa[x] = find(fa[x]); 19 shift[x] += shift[p]; 20return fa[x]; 21} 2223void move_to(int u, int v) 24{ 25 u = find(u) , v =find(v); 26if(u==v) return ; 27 fa[u] = v; 28 num[v] += num[u]; 29 shift[u]++; 30} 3132void solve() 33{ 34 scanf("%d%d", &n, &m); 35 init(); 36char s[3]; 37int u, v; 38 printf("Case %d:\n", cas++); 39while(m--) 40 { 41 scanf("%s%d", s, &u); 42if(s[0]==‘T‘){ 43 scanf("%d", &v); 44 move_to(u, v); 45 } 46else{ 47 v =find(u); 48 printf("%d %d %d\n", v, num[v], shift[u]); 49 } 50 } 51} 5253int main() 54{ 55// freopen("in.txt", "r", stdin);56 cin>>_; 57while(_--) solve(); 58return0; 59 }
view code #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; constint N = 10010; int _, cas=1, n, m, fa[N], shift[N]; int find(int x) { if(fa[x]<0) return x; int p = fa[x]; fa[x] = find(fa[x]); shift[x] += shift[p]; return fa[x]; } void move_to(int u, int v) { u = find(u) , v =find(v); if(u==v) return ; fa[v] += fa[u]; fa[u] = v; shift[u]++; } void solve() { scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) fa[i]=-1, shift[i]=0; char s[3]; int u, v; printf("Case %d:\n", cas++); while(m--) { scanf("%s%d", s, &u); if(s[0]==‘T‘){ scanf("%d", &v); move_to(u, v); } else{ v =find(u); printf("%d %d %d\n", v, -fa[v], shift[u]); } } } int main() { // freopen("in.txt", "r", stdin); cin>>_; while(_--) solve(); return 0; }
原文:http://www.cnblogs.com/zyx1314/p/3873031.html
内容总结
以上是互联网集市为您收集整理的hdu 3635 Dragon Balls(并查集)全部内容,希望文章能够帮你解决hdu 3635 Dragon Balls(并查集)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。