[HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)

发布于 2018-02-07  69 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)

Description

Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.
Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).
And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

Http

HDU
ZOJ
SCU
Luogu

Tag

左偏树,并查集

题目大意

有若干只猴子,开始互相都不认识,两只不认识的猴子会从让它们认识的猴子中最厉害的猴子来打一架,然后就互相认识了。打架的猴子厉害值除以二,求每一次打完架后这些刚刚认识的猴子中最厉害的。

解决思路

左偏树实现可并堆,每次取堆顶分离出来,除以二再加进去,合并堆。并查集维护一只猴子所在的堆的根方便查找。

代码

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

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100100;
const int inf=2147483647;

class HeapData
{
public:
    int key;
    int ch[2],dis;
    void init()
        {
            ch[0]=ch[1]=dis=0;
            return;
        }
};

int n,m;
int UFS[maxN];//并查集
HeapData H[maxN];

int Merge(int x,int y);//左偏树合并
void Div(int x);//把x(保证是一棵左偏树的根)的值除以二再放回去
int Find(int x);

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++) scanf("%d",&H[i].key),H[i].init(),UFS[i]=i;
        int m;scanf("%d",&m);
        while (m--)
        {
            int x,y;scanf("%d%d",&x,&y);
            if (Find(x)==Find(y))
            {
                printf("-1\n");
                continue;
            }
            x=Find(x);y=Find(y);
            if (H[x].key<H[y].key) swap(x,y);
            Div(x);Div(y);x=Find(x);y=Find(y);//堆顶除以二后再找到新的堆顶
            int nrt=Merge(x,y);//合并
            UFS[x]=UFS[y]=nrt;
            printf("%d\n",H[nrt].key);
        }
    }
}

int Merge(int x,int y)
{
    if (x==0) return y;
    if (y==0) return x;
    if (H[x].key<H[y].key) swap(x,y);
    H[x].ch[1]=Merge(H[x].ch[1],y);
    if (H[H[x].ch[0]].dis<H[H[x].ch[1]].dis) swap(H[x].ch[0],H[x].ch[1]);
    if (H[x].ch[1]) H[x].dis=H[H[x].ch[1]].dis+1;
    else H[x].dis=0;
    return x;
}

void Div(int x)
{
    if ((H[x].ch[0]==0)&&(H[x].ch[1]==0))//特判只有一个元素的情况
    {
        H[x].key/=2;
        return;
    }
    int nrt=Merge(H[x].ch[0],H[x].ch[1]);//先把左右子树合并
    UFS[nrt]=nrt;UFS[x]=x;//修改并查集
    if (nrt==H[x].ch[0]) if (H[x].ch[1]) UFS[H[x].ch[1]]=nrt;
    if (nrt==H[x].ch[1]) if (H[x].ch[0]) UFS[H[x].ch[0]]=nrt;
    H[x].init();H[x].key/=2;//分离出来后,处理根
    int nnrt=Merge(x,nrt);//再把根合并回去
    UFS[nrt]=UFS[x]=nnrt;//再修改并查集关系
    return;
}

int Find(int x)
{
    if (UFS[x]!=x) UFS[x]=Find(UFS[x]);
    return UFS[x];
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)


HNCJ OIer