• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-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ǎ崽 閱讀(1058) 評論(0)  編輯 收藏 引用
            久久亚洲高清综合| 一本大道久久a久久精品综合| 久久久无码精品午夜| 久久综合久久伊人| 久久不见久久见免费视频7| 色综合久久久久| 国产美女亚洲精品久久久综合| 国产精品久久波多野结衣| 欧美麻豆久久久久久中文| 久久婷婷国产综合精品| 久久精品无码专区免费| 2021少妇久久久久久久久久| 日本精品久久久久影院日本| 99久久精品午夜一区二区| 亚洲精品97久久中文字幕无码| 丰满少妇人妻久久久久久| 国产精品久久久久久久久久影院| 99精品久久精品| 性做久久久久久久| 久久久久99这里有精品10 | 人妻丰满?V无码久久不卡| 乱亲女H秽乱长久久久| 99久久综合国产精品二区| 亚洲精品白浆高清久久久久久 | 99久久亚洲综合精品成人| 久久久一本精品99久久精品88| 93精91精品国产综合久久香蕉| 久久99国产精品尤物| 亚洲国产精品无码久久久蜜芽| 国内精品伊人久久久影院| 久久一本综合| 亚洲一级Av无码毛片久久精品| 久久国产影院| 久久亚洲精品无码播放| 久久久亚洲精品蜜桃臀| 欧美久久天天综合香蕉伊| 日日狠狠久久偷偷色综合免费| 欧美大战日韩91综合一区婷婷久久青草| 国产美女久久久| 久久福利青草精品资源站| 久久综合狠狠色综合伊人|