LUOGU P1196 [NOI2002]银河英雄传说

传送门

解题思路

带权值的并查集。front[x]表示x前面有几个战舰，num[x]表示所在列战舰的个数，然后front在回溯是修改。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int MAXN = 30005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

int T,num[MAXN],fa[MAXN],front[MAXN];

int get(int x){
    if(x==fa[x]) return x;
    int now=get(fa[x]);
    front[x]+=front[fa[x]];
    return fa[x]=now;
}

int main(){
    T=rd();int x,y;char c;
    for(int i=1;i<=30000;i++) fa[i]=i,num[i]=1;
    while(T--){
        cin>>c;x=rd(),y=rd();
        int u=get(x),v=get(y);
        if(c=='M'){
            fa[u]=v;front[u]+=num[v];
            num[v]+=num[u];num[u]=0;
        }
        else {
            if(u!=v) puts("-1");
            else printf("%d
",abs(front[y]-front[x])-1);
        }
    }
    return 0;
}