P1196 [NOI2002] 银河英雄传说

使用带权并查集维护：

  1. 每个战舰所属列。
  2. 每个战舰到当前列第一个战舰的距离。
  3. 每列的战舰数量。

  • 如何求同列战舰之间相隔的战舰数量？

    使用两战舰到当前列头部的距离之差减1即可得到。

  • 如何在并查集合并时维护每个战舰到当前列第一个战舰的距离？

    当前点到当前点合并前的祖先的距离与祖先到链头的点距离相加，在find祖先递归的回溯过程中更新（只有find操作路径压缩会改变祖先）。

  • 每一次合并操作：把x的祖先(链头)插到y的链尾后面，更新x原链头到现链头(y链头)的距离，更新y所在列的大小。

    注意每次把x合并到y后面时，x的祖先就要变成y的祖先，顺序不能反，否则会打乱维护的2、3性质。

/*P1196 [NOI2002] 银河英雄传说使用带权并查集维护：1.每个战舰所属列 2.每个战舰到当前列第一个战舰的距离 3.每列的战舰数量- 如何求同列战舰之间相隔的战舰数量？使用两战舰到当前列头部的距离之差减1即可得到。- 如何在并查集合并时维护每个战舰到当前列第一个战舰的距离？  当前点到当前点合并前的祖先的距离与祖先到链头的点距离相加，在find祖先递归的回溯过程中更新（只有find操作路径压缩会改变祖先） - 每一次合并操作：把x的祖先(链头)插到y的链尾后面，更新x原链头到现链头(y链头)的距离，更新y所在列的大小 注意每次把x合并到y后面时，x的祖先就要变成y的祖先，顺序不能反，否则会打乱维护的2、3性质*/#include#include#include#includeusing namespace std;const int N=100000;int f[N],dis[N],siz[N];//并查集；到链头的距离；当前链的长度int find(int x)//每次查询会更改祖先，必须维护dis {if(f[x]==x) return x;int fu=find(f[x]);dis[x]+=dis[f[x]];//原来dis存的是它到自己原来祖先(f[x])的距离，现在只需要加上其祖先到链头的距离return f[x]=fu; }int main(){for(int i=1;i>op; scanf("%d%d",&x,&y);int fx=find(x),fy=find(y);if(op=='M'){dis[fx]+=siz[fy];//x的祖先(链头)插到y的链尾后面，x原链头到现链头(y链头)距离更新f[fx]=fy;//x合并到y后面，x的祖先变成y的祖先，顺序不能反siz[fy]+=siz[fx];//更新y所在列的大小 siz[fx]=0;//清零实际上可有可无， }if(op=='C'){if(fx!=fy) printf("-1\n");else printf("%d\n",abs(dis[x]-dis[y])-1);}}return 0;}