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)//返回的是樹的根節(jié)點
{
if(!x) //x是空樹
return y; //返回的就是y樹的根節(jié)點
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)//返回的是樹的根節(jié)點
{
int l,r;
hh[k].pow >>= 1;
l = hh[k].left;
r = hh[k].right;//節(jié)點單獨拿出來
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);//把這個節(jié)點加進合并出來的樹
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);//找根節(jié)點
y = find(b);//找根節(jié)點
if(x==y)
puts("-1");
else
{
x = maxpow(x);//處理x的根節(jié)點，并返回處理后的根節(jié)點
y = maxpow(y);
k = unite(x,y);//合并兩顆樹
printf("%d\n",hh[k].pow);
}
}
}
return 0;
}
合并的時候的步驟
0.其中一顆樹為空的話返回另外一個
1.將x確定為主樹(交換xy)
2.合并x的右兒子和y
3.合并出來的根節(jié)點的father指向x
4.保證左兒子深度大于右兒子
還有一道：
http://acm.hdu.edu.cn/showproblem.php?pid=1434
posted on 2009-03-18 18:14
shǎ崽 閱讀(1067)
評論(0) 編輯 收藏 引用