首页 > 代码库 > zoj2334 Monkey King , 并查集,可并堆,左偏树

zoj2334 Monkey King , 并查集,可并堆,左偏树

提交地址:点击打开链接

题意:  N(N<=10^5)只猴子,初始每只猴子为自己猴群的猴王,每只猴子有一个初始的力量值。这些猴子会有M次会面。每次两只猴子x,y会面,若x,y属于同一个猴群输出-1,否则将x,y所在猴群的猴王的力量值减半,然后合并这两个猴群。新猴群中力量值最高的为猴王。输出新猴王的力量值。


分析:涉及集合的查询,合并,取最值。 利用并查集和左偏树即可解决。


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 200000;
int tot, v[maxn], l[maxn], r[maxn], d[maxn], f[maxn];
int findset(int x)
{return f[x]==x?x:f[x]=findset(f[x]);}
int Merge(int x, int y)
{
    if(!x) return y;
    if(!y) return x;
    if(v[x] < v[y]) swap(x, y);  //大顶堆
    r[x] = Merge(r[x], y); //递归合并右子树和Y
    f[r[x]] = x;  //更新T右子树的根
    if(d[l[x]] < d[r[x]]) //维护堆性质
        swap(l[x], r[x]);
    d[x] = d[ r[x] ] + 1;
    return x;
}
int Init(int x)
{
    tot++;
    v[tot] = x;
    f[tot] = tot;
    l[tot] = r[tot] = d[tot] = 0;
}
int Insert(int x, int y)
{
    return Merge(x, Init(y));
}
int Top(int x)
{
    return v[x];
}
int Pop(int x)
{
    int L = l[x], R = r[x];
    f[L] = L;
    f[R] = R;
    v[x] /= 2;
    r[x] = l[x] = d[x] = 0;
    return Merge(L, R);
}
void solve(int x, int y)
{
    int left = Pop(x), right = Pop(y);
    left = Merge(left, x);
    right = Merge(right, y);
    left = Merge(left, right);
    printf("%d\n", Top(left));
}
int main()
{
    int n, m, i, x, y;
    while(~scanf("%d", &n))
    {
        tot = 0;
        for(i=1; i<=n; ++i)
        {
            scanf("%d",&x);
            Init(x);
        }
        scanf("%d", &m);
        for(i=1; i<=m; ++i)
        {
            scanf("%d%d", &x, &y);
            int fx = findset(x), fy = findset(y);
            if(fx==fy)
            {
                printf("-1\n");
            }
            else
            {
                solve(fx, fy);
            }
        }
    }
    return 0;
}
/*
5
20
16
10
10
4
5
2 3
3 4

8
5
5
-1
10
*/