HDU 1512 Monkey King(左偏树模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=1512

题意:

有n只猴子,每只猴子一开始有个力量值,并且互相不认识,现有每次有两只猴子要决斗,如果认识,就不打了,否则的话,这两只都会从它们所认识的猴子中派出一只力量值最大的猴子出来,并且这只猴子的力量值会减半,在打过之后,这两只猴子所在的集体就都认识了。

思路:
这是一道左偏树的模板题。

每个节点有5个值,l为左儿子节点,r为右儿子节点,fa为父亲节点(父亲节点的用法与并查集相似),val为优先级(这道题目就是大根堆),dis是距离值(在两棵树合并的时候使用,根据dis来决定左右子树是否需要对换)。

一开始每只猴子就是一棵树,每次决斗就是将两棵树进行合并。

 #include<iostream>
#include<cstdio>
using namespace std;
const int maxn = +; int n, m; struct Heap
{
int l,r,fa,val,dis;
}t[maxn]; int finds(int x)
{
return t[x].fa == -? x:t[x].fa = finds(t[x].fa);
} int merge(int x, int y)
{
if(x == ) return y; //如果为0的话,就说明是空子树,根节点当然就是另一节点了
if(y == ) return x;
if(t[y].val>t[x].val) swap(x,y); //始终往右子树进行插入
t[x].r = merge(t[x].r,y);
t[t[x].r].fa = x;
if(t[t[x].l].dis < t[t[x].r].dis) swap(t[x].l,t[x].r); //是否需要左右子树的对换,这样是为了右子树尽量短
if(t[x].r == ) t[x].dis = ; //距离的重新分配
else t[x].dis = t[t[x].r].dis + ;
return x;
} int pop(int &root)
{
int l = t[root].l;
int r = t[root].r;
t[root].l = t[root].r = t[root].dis = ;
t[root].fa = -;
t[l].fa = t[r].fa = -; //删除root根节点
return merge(l,r); //这样一来相当于分裂成了两棵子树,重新进行合并,最后返回值为合并后的根节点
} int push(int x, int y)
{
return merge(x,y);
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
{
t[i].l=t[i].r=t[i].dis=;
t[i].fa=-;
scanf("%d",&t[i].val);
}
scanf("%d",&m);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
int x=finds(a);
int y=finds(b);
if(x!=y)
{
t[x].val/=;
int xx = push( pop(x),x);
t[y].val/=;
int yy = push( pop(y),y);
printf("%d\n",t[merge(xx,yy)].val);
}
else puts("-1");
}
}
return ;
}
上一篇:hadoop教程


下一篇:Android设置TextView行间距(非行高)