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