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 ;

 }

HDU 1512 Monkey King（左偏树模板题）的相关教程结束。