[ NOI 2002 ] 银河英雄传说

$\\$

Description

有 $n$ 列战场，每一列一开始只有一个战舰，编号就是对应的战场编号。

有 $m$ 次操作：

$M_{i,j}$ ：把 $i$ 所在的一整列接在 $j$ 所在的一列的最后面。
$C_{i,j}$ ：查询 $i,j$ 是否在同一列里，若在的话输出两者之间隔了多少个战舰。

注意每一列战场的战舰都是排成一列的。

$\\$

Solution

带偏移量的并查集。

记录 $d[x]$ 表示 $x$ 到所在列头的一段上共有多少个战舰。

记录 $sz[x]$ 表示 $x$ 所在的一列有多少个战舰。

为了保证复杂度，我们在做的时候还是要路径压缩。

但是 $d[x]$ 怎么保证正确？递归的时候这么写就好了。

int find(int x){

    if(x==f[x]) return x;

    int fa=find(f[x]);

    d[x]+=d[f[x]];

    return f[x]=fa;

  }

注意是 $d[x]+=d[f[x]]$，因为之前可能路径压缩过。还有注意 $f[x] $ 的更新时间。

合并的时候，记 $f_i$ 表示 $i$ 所在一列的列头，$f_j$ 表示 $j$ 所在的列头，有

\[d[f_i]=sz[f_j]
\]

查询的时候，$find$ 的过程中已经保证了两位置的 $d$ 数组数值正确，所以在一列的两个战舰答案就是

\[|d[x]-d[y]|-1
\]

$\\$

Code

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 30010

#define R register

#define gc getchar

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

struct UFS{

  int f[N],d[N],sz[N];

  UFS(){for(R int i=1;i<N;++i){f[i]=i;sz[i]=1;}}

  int find(int x){

    if(x==f[x]) return x;

    int fa=find(f[x]);

    d[x]+=d[f[x]];

    return f[x]=fa;

  }

  inline void merge(int x,int y){

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

      d[fx]=sz[fy]; f[fx]=fy; sz[fy]+=sz[fx];

  }

}ufs;

int main(){

  char op;

  int t=rd(),x,y;

  while(t--){

    op=gc(); while(!isalpha(op)) op=gc();

    if(op=='M'){x=rd();y=rd();ufs.merge(x,y);}

    else{

      x=rd(); y=rd();

      if(ufs.find(x)!=ufs.find(y)) puts("-1");

      else printf("%d\n",abs(ufs.d[x]-ufs.d[y])-1);

    }

  }

  return 0;

}

巴特西

[ NOI 2002 ] 银河英雄传说

Description

Solution

Code

最新文章

热门文章