Luogu P1196 [NOI2002]银河英雄传说

时间：2023-03-09 08:54:42
Luogu P1196 [NOI2002]银河英雄传说

　　一年没写博客了（滑稽）。

　　这道题很玄学，导致自己都有一个坑人的问题求解。如果有大佬有能力求帮助：https://www.luogu.org/discuss/show?postid=30231

　　再来讲一下我对这道题的理解吧。

　　首先，对于判断两个数是否在同一列战舰中，我们只需要朴素的并查集就可以。

　　但这道题还要求我们去搞一个两船之间的距离（这就很难办了），所以只能使用带权并查集。

　　我们开一个数组front[]，来表示第i号战舰到i所在的战舰的队头的距离。这样如果两个战舰在同一列中，他们的距离就是abs(front[i]-front[j])-1（因为这两辆都不包括，因此-1）。

　　这样是很方便，但当我们合并时，就会发生front[]值失去对应性。所以我们要不断地更新front[]。

　　再开一个数组len[]表示以i为队头的队列的长度，这样在把i接到j后面时，只需要让front[fi]+=len[fj]，并把len[fj]清零即可。

　　最后对于front[]的更新，只需要在getfather时回溯完成即可。

　　然后你就学会了如何打带权并查集（欧耶）！

　　CODE

#include<cstdio>

using namespace std;

const int N=;

int father[N],front[N],len[N],i,t,x,y;

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(int x)

{

    if (x<) putchar('-'),x=-x;

    if (x/) write(x/);

    putchar(x%+'');

}

inline int getfather(int k)

{

    if (father[k]==k) return k;

    int fa=getfather(father[k]);

    front[k]+=front[father[k]];

    return father[k]=fa;

}

inline int abs(int a) { return a<?-a:a; }

int main()

{

    //freopen("testdata.in","r",stdin); freopen("my_out.out","w",stdout);

    for (i=;i<N;++i)

    father[i]=i,len[i]=;

    read(t);

    while (t--)

    {

        char ch=getchar();

        while (ch!='M'&&ch!='C') ch=getchar();

        read(x); read(y);

        int fx=getfather(x),fy=getfather(y);

        if (ch=='M')

        {

            front[fx]+=len[fy];

            father[fx]=fy;

            len[fy]+=len[fx];

            len[fx]=;

        } else write(fx==fy?abs(front[x]-front[y])-:-),putchar('\n');

    }

    return ;

}

相关文章