使用带权并查集维护：
- 每个战舰所属列。
- 每个战舰到当前列第一个战舰的距离。
- 每列的战舰数量。
-
如何求同列战舰之间相隔的战舰数量？
使用两战舰到当前列头部的距离之差减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<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using 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<=30000;i++) f[i]=i,siz[i]=1;
int t,x,y;
char op;
scanf("%d",&t);
while(t--)
{
cin>>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("-1n");
else printf("%dn",abs(dis[x]-dis[y])-1);
}
}
return 0;
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
