hdu3635 Dragon Balls(帶權并查集)

 1 /*
 2    題意：有N個城市， 每一個城市都有一個龍珠（編號與城市的編號相同），有兩個操作
 3    T A ,B 將標號為A龍珠所在城市的所有的龍珠移動到B龍珠所在城市中！ 
 4    
 5    思路：并查集 （壓縮路徑的時候將龍珠移動的次數進行更新） 
 6 */
 7 #include<iostream> 
 8 #include<cstring>
 9 #include<cstdio>
10 #include<algorithm>
11 #define M 10005
12 using namespace std;
13 
14 int f[M];//表示龍珠 i 所在的城市標號 
15 int Tcnt[M];//記錄每個龍珠移動的次數 
16 int Scnt[M];//記錄每個城市中龍珠總個數 
17 
18 int getFather(int x){
19    if(x==f[x])
20      return x;
21    
22    int ff=getFather(f[x]); 
23    Tcnt[x]+=Tcnt[f[x]];//每一個龍珠移動的次數+=其依附的父親龍珠移動的次數 
24    f[x]=ff;
25    return f[x]; 
26 }
27 
28 void Union(int a, int b){
29    int fa=getFather(a);
30    int fb=getFather(b);
31    if(fa==fb) return;
32    f[fa]=fb;
33    Scnt[fb]+=Scnt[fa];//將fa城市的龍珠全部移動到fb城市中！ 
34    Scnt[fa]=0;
35    Tcnt[fa]+=1;//a球移動次數+1 
36 } 
37 
38 int main(){
39    int t, a, b;
40    int n, m;
41    char ch[2];
42    scanf("%d", &t);
43    for(int cc=1; cc<=t; ++cc){
44           printf("Case %d:\n", cc); 
45        scanf("%d%d", &n, &m);
46        memset(Tcnt, 0, sizeof(int)*(n+1));
47        for(int i=1; i<=n; ++i)
48           f[i]=i, Scnt[i]=1;
49        while(m--){
50           scanf("%s", ch);
51           if(ch[0]=='T'){
52              scanf("%d%d", &a, &b);
53              Union(a, b); 
54           }
55           else {
56              scanf("%d", &a);
57              int ff = getFather(a);
58              printf("%d %d %d\n", ff, Scnt[ff], Tcnt[a]); 
59           }          
60        }
61    } 
62    return 0;
63 }

轉載于:https://www.cnblogs.com/hujunzheng/p/3902119.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531771.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531771.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531771.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！