首页 > 代码库 > HDU 3635 延缓更新的并查集

HDU 3635 延缓更新的并查集

2024-07-12 22:18:10   220人阅读

Dragon Balls

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2839    Accepted Submission(s): 1097


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
 
 
作为龙珠的铁杆粉丝，这道题必须A，否则就对不起自己的偶像了。。
题目意思  ：
初始时有编号为1-n的龙珠分别放入编号为1-n的城市中，对龙珠有两种操作   输入为T X Y时，即把编号为X的龙珠所在城市里的所有龙珠都移动到编号为Y的龙珠所在的城市。
输入为为Q X 时即查询编号为X的龙珠目前所在的城市编号，所在城市中有多少个龙珠，编号为X的龙珠共移动了多少次。
 
思路：
很显然是用并查集，题目中这样一句话“ All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. ”，即说明每个城市只能移动一次就成空城了就不能接纳龙珠了，从而可以说明若以土著龙珠（即初始化时就在这个城市里的龙珠）为根结点，那么编号x的龙珠目前所在城市==fiindroot（x）。
城市编号就求出来了。
 
咱们用一个数组num[i]表示第i座城市里的龙珠数目，那么每次把第j座城市的龙珠移到第i座城市中，第i座城市里龙珠数目为num[i]+=num[j]。
所在城市的龙珠数目也就这么容易的求出了。
 
 
比较麻烦的是求编号为X的龙珠的移动次数。
因为移动的龙珠和求的龙珠编号可能不同，若枚举所有龙珠编号则超时。
有一个很巧的方法（我没想出来，看解题报告才知道。。。），咱们用time[i]表示编号为i的龙珠移动的次数，每次需要用到编号i的龙珠的时候，就压缩路径把从i到土著龙珠（根结点）路径上所有结点的time[]都加到time[i]上，因为每次移动都是根结点移动然后再与另外的根结点相合并即整体合并，每次移动都顺带着结点 i 移动，所以从i到根结点所有结点都与结点 i 有顺带关系，用完这些顺带关系即time[i]已求出后就舍弃这些中间点，使 i 指向新的根结点从而保证用过的顺带关系不会重复使用。
 
是不是有些一头雾水呢？  其实我刚开始看的时候也是这样。。没关系，贴出代码，自己弄几个例子调试跟踪下就懂了。
 
代码：
 
 
 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6  7  8 int father[10005]; 9 int timee[10005];10 int num[10005];11 12 int findroot(int p){13     if(p==father[p]) return p;14     int f=father[p];15     father[p]=findroot(father[p]);16     timee[p]+=timee[f];   //把沿途上所有与点p有顺带关系的点的移动次数加到点p上 （好好调试跟踪下） 17     return father[p];18 }19 20 void unsion(int x,int y){21     int fx=findroot(x);22     int fy=findroot(y);23     if(fx!=fy){                   //每次都以新的土著龙珠为根结点 24         num[fy]+=num[fx];25         father[fx]=fy;26         timee[fx]=1;27     }28 }29 30 main()31 {32     int t, i, j, x, y,     n, Q, kase=1;33     char s[10];34     cin>>t;35     while(t--){36         scanf("%d %d",&n,&Q);37         printf("Case %d:\n",kase++);38         for(i=1;i<=n;i++){39             father[i]=i;40             timee[i]=0;41             num[i]=1;42         }43         while(Q--){44             scanf("%s",s);45             if(strcmp(s,"T")==0){46                 scanf("%d %d",&x,&y);47                 unsion(x,y);48             }49             else {50                 scanf("%d",&x);51                 int fx=findroot(x);52                 printf("%d %d %d\n",fx,num[fx],timee[x]);53             }54         }55     }56 }

 


联系
我们