HDU-3635 -Dragon Balls【带权并查集】题解

墨蓝 2021-07-24 23:49 359阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.题意
         *  3.思路
         *  4.代码

### 1.题目 ###

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.

![在这里插入图片描述][2020060118373733.png]  
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

### 2.题意 ###

每次给出一个龙珠的序号。你必须告诉他球在哪个城市，在那个城市有多少个龙珠，你还需要告诉他球已经被运送了多少次。

### 3.思路 ###

**带权并查集**。city\[i\]记录每个城市有多少个龙珠。fa\[i\]记录i的父节点。tra\[i\]记录龙珠被转移的次数。第一个问题：球在哪个城市。只需找到球的父节点即可。第二个问题：在那个城市有多少个龙珠。city\[i\]记录的就是。第三个问题：球已经被运送了多少次。tra\[i\]j记录的就是。详细解释看代码。

### 4.代码 ###

#define _CRT_SECURE_NO_WARNINGS 
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e4 + 10;
    int city[maxn],fa[maxn],tra[maxn];
    void init(int n)///初始化
    { 
    	for (int i = 0; i <= n; i++)
    	{ 
    		fa[i] = i;
    		city[i] = 1;  //每个城市最开始只有一个龙珠
    		tra[i] = 0;  //最开始每个球的转移次数为0
    	}
    }
    int find(int x) //查找
    { 
    	if (x != fa[x])
    	{ 
    		int tmp = fa[x];
    		fa[x] = find(fa[x]);  ///路径压缩
    		tra[x] += tra[tmp];   //x节点的转移次数+x父节点的转移次数=x龙珠到最终城市(根节点)的转移次数
    	}
    	return fa[x];
    }
    void merge(int i, int j) //合并
    { 
    	int x = find(i), y = find(j);
    	if (x != y)
    	{ 
    		fa[x] = y;
    		tra[x] = 1;  //每合并一次都意味着转移一次
    		city[y] += city[x];//合并后的y城市的龙珠数=x城的龙珠数+原来y城的龙珠数
    		city[x] = 0;  //被合并的城市龙珠数清零
    	}
    }
    
    int main()
    { 
    	int T;
    	scanf("%d", &T);
    	int cas = 0;
    	while (T--)
    	{ 
    		char str[3];
    		int a, b,n,m;
    		scanf("%d %d", &n, &m);
    		printf("Case %d:\n", ++cas);
    		init(n);
    		while (m--)
    		{ 
    			scanf("%s", str);
    			if (str[0] == 'T')
    			{ 
    				scanf("%d%d", &a, &b);
    				merge(a, b);
    			}
    			else
    			{ 
    				scanf("%d", &a);
    				int pa = find(a);
    				printf("%d %d %d\n",pa,city[pa], tra[a]);
    			}
    		}
    		
    
    	}
    	return 0;
    }

[2020060118373733.png]: /images/20210724/7f67d3b891a44540a4b558f2da688ff8.png