ZOJ2334 Monkey King 左偏树

ZOJ2334

用左偏树实现优先队列最大的好处就是两个队列合并可以在Logn时间内完成 用来维护优先队列森林非常好用。

左偏树代码的核心也是两棵树的合并!

代码有些细节需要注意。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=200000;

struct monkey{

	int num;int group;int strong;int ls; int rs;int dist;

};

int n,m,tot;

monkey mon[maxn];

int find(int x)

{

 if(mon[x].group==x||mon[x].group==0)return x;

 	else return mon[x].group=find(mon[x].group);

}

int Top(int x)

{

 return find(x);

}

int Merge(int x,int y)

{

 if(x==y)return x;

 if(!x)return mon[y].group=y;

 if(!y)return mon[x].group=x;

 if(mon[x].strong<mon[y].strong)swap(x,y);

 mon[x].rs=Merge(mon[x].rs,y);

 mon[mon[x].rs].group=x;

 if(mon[mon[x].ls].dist<mon[mon[x].rs].dist)swap(mon[x].ls,mon[x].rs);

 mon[x].dist=mon[mon[x].rs].dist+1;

 return mon[x].group=x;

}

int Pop(int x)

{

 mon[x].group=Merge(mon[x].ls,mon[x].rs);

 mon[x].ls=mon[x].rs=mon[x].dist=0;

}

void Insert(int x,int y)

{

 Merge(find(x),y);

}

int main()

{freopen("t.txt","r",stdin);

 //freopen("1.txt","w",stdout);

tot=0;

 while(scanf("%d",&n)!=EOF)

 {

  tot++;

  memset(mon,0,sizeof(mon));

  for(int i=1;i<=n;i++)

  	 {

  	   mon[i].num=mon[i].group=i;mon[i].ls=mon[i].rs=mon[i].dist=0;

  	   scanf("%d",&mon[i].strong);

	 }

  scanf("%d",&m);

  int a,b;

  for(int i=1;i<=m;i++)

     {

     	scanf("%d%d",&a,&b);

     	a=find(a);b=find(b);

     	if(a==b){printf("-1\n");continue;}

     	mon[a].strong/=2;mon[b].strong/=2;

     	Pop(a);

		 Pop(b);

     	Insert(find(a),a);

		 Insert(find(b),b);

     	printf("%d\n",max(mon[find(a)].strong,mon[find(b)].strong));

     	Merge(find(a),find(b));

	 }

 }

 return 0;

}