HDU 3635 Dragon Balls(带权并查集) - c++编程基础

TOP

HDU 3635 Dragon Balls(带权并查集)

2015-07-20 17:33:53 来源: 作者: 【大中小】浏览:2次

Tags：HDU 3635 Dragon Balls 查集

题目地址：HDU 3635

加权并查集水题。

用num数组维护该城市有多少龙珠，用times数组维护每个龙珠运输了多少次。num数组在合并的时候维护。times数组由于每个都不一样，所以要在找根的时候递归来全部维护。

最终，x龙珠所在的城市就是x节点所在的根，x结点所在的跟的num数组值是该城市的龙珠数。times[x]为该龙珠运输了多少次。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; #define LL long long int bin[20000], num[20000], times[20000]; int find1(int x) { int y; if(bin[x]!=x) { y=bin[x]; bin[x]=find1(bin[x]); times[x]+=times[y]; } return bin[x]; } void join(int x, int y) { int f1=find1(x); int f2=find1(y); if(f1!=f2) { bin[f1]=f2; num[f2]+=num[f1]; times[f1]++; } } int main() { int t, nn=0, n, m, i, a, b, f; char c; scanf("%d",&t); while(t--) { nn++; scanf("%d%d",&n,&m); for(i=1; i<=n; i++) { bin[i]=i; num[i]=1; times[i]=0; } printf("Case %d:\n",nn); while(m--) { getchar(); scanf("%c",&c); if(c=='T') { scanf("%d%d",&a,&b); join(a,b); } else { scanf("%d",&a); f=find1(a); printf("%d %d %d\n",f,num[f],times[a]); } } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：BZOJ 3110 ZJOI2013 K大数查询树..	下一篇：BZOJ1041 圆上的整点 Solution

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: