ZOJ2334 Monkey King 并查集 STL

题意：两家原始人（猴）打交道后成为一家猴，打交道时两家分别派出最帅的两位猴子，颜值各自减半，问每次打交道后新家族最帅的猴子的颜值。当然，已经是一家子就没有必要打交道了，因为没有猴希望颜值降低，毕竟还得靠这个吃饭。

裸裸的并查集+大根堆：

由于在下写的queue，需要重量优化，不然超时

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct in{
    int str; 
    in( int a=0 ):str(a){}
};
priority_queue<in>q[100010];
int fa[100010];
bool operator < (const in a,const in b)
{
	return a.str<b.str;
}
int _find(int v)
{
	if(v==fa[v]) return v;
	fa[v]=_find(fa[v]);
	return fa[v];
}
void _merge(int u,int v)
{
	in t=q[u].top();q[u].pop();
	q[u].push(t.str/2);
	t=q[v].top();q[v].pop();
	q[v].push(t.str/2);
    if(q[u].size()>q[v].size()) {//重量优化
		int tmp=u;u=v;v=tmp;
    }
    fa[u]=fa[v];
    while(!q[u].empty()){
		in t=q[u].top();q[u].pop();
		q[v].push(t);
    }
    t=q[v].top();
    printf("%d
",t.str);
}

int main()
{
	int n,m,x,y,i;
	while(~scanf("%d",&n))
	{
		for(i=1;i<=n;i++){
			while(!q[i].empty()) q[i].pop();
			scanf("%d",&x);
			fa[i]=i;
			q[i].push(x);
		}
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&x,&y);
			x=_find(x);
			y=_find(y);
			if(x==y) printf("-1
");
			else _merge(x,y);
		}
	}
	return 0;
}