随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=1512


#include<stdio.h>
#define MAX 100001

struct Left_Heap{
    
int left,right;
    
int father;
    
int pow;
    
int deep;
}hh[MAX];

int find(int a)
{
    
while(a!=hh[a].father)
        a 
= hh[a].father;
    
return a;
}
int unite(int x,int y)//返回的是树的根节点
{
    
if(!x)            //x是空树
        return y;    //返回的就是y树的根节点
    if(!y)
        
return x;
    
if(hh[x].pow < hh[y].pow)            //以x树主树,y插入
        x^=y^=x^=y;
    hh[x].right 
= unite(hh[x].right,y);    //合并y和x的右子树
    hh[ hh[x].right ].father = x;        //x的右子树的父亲是x(这不是废话嘛)
    if(hh[ hh[x].left ].deep < hh[ hh[x].right ].deep)//保证左子深度要比右子树大
        hh[x].left ^= hh[x].right ^= hh[x].left ^= hh[x].right;
    hh[x].deep 
= hh[ hh[x].right ].deep + 1;
    
return x;
}
int maxpow(int k)//返回的是树的根节点
{
    
int l,r;
    hh[k].pow 
>>= 1;
    l 
= hh[k].left;
    r 
= hh[k].right;//节点单独拿出来
    hh[l].father = l;
    hh[r].father 
= r;//左右儿子分别成树
    hh[k].left = hh[k].right = hh[k].deep = 0;//变成没有左右儿子
    l = unite(l,r);//合并原来的左右儿子
    k = unite(l,k);//把这个节点加进合并出来的树
    return k;
}
int main()
{
    
int n,i,m,a,b,x,y,k;
    
while(scanf("%d",&n)==1)
    {
        
for(i=1;i<=n;i++)
        {
            scanf(
"%d",&hh[i].pow);
            hh[i].father 
= i;
            hh[i].left 
= hh[i].right = hh[i].deep = 0;
        }
        scanf(
"%d",&m);
        
while(m--)
        {
            scanf(
"%d%d",&a,&b);
            x 
= find(a);//找根节点
            y = find(b);//找根节点
            if(x==y)
                puts(
"-1");
            
else
            {
                x 
= maxpow(x);//处理x的根节点,并返回处理后的根节点
                y = maxpow(y);
                k 
= unite(x,y);//合并两颗树
                printf("%d\n",hh[k].pow);
            }
        }
    }
    
return 0;
}



合并的时候的步骤
0.其中一颗树为空的话返回另外一个
1.将x确定为主树(交换xy)
2.合并x的右儿子和y
3.合并出来的根节点的father指向x
4.保证左儿子深度大于右儿子

还有一道:
http://acm.hdu.edu.cn/showproblem.php?pid=1434
posted on 2009-03-18 18:14 shǎ崽 阅读(1032) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理