P1196 [NOI2002] 银河英雄传说带权并查集-Toy模板网

这篇具有很好参考价值的文章主要介绍了P1196 [NOI2002] 银河英雄传说带权并查集。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

P1196 [NOI2002] 银河英雄传说

使用带权并查集维护：

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

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

使用两战舰到当前列头部的距离之差减1即可得到。
如何在并查集合并时维护每个战舰到当前列第一个战舰的距离？

当前点到当前点合并前的祖先的距离与祖先到链头的点距离相加，在find祖先递归的回溯过程中更新（只有find操作路径压缩会改变祖先）。
每一次合并操作：把x的祖先(链头)插到y的链尾后面，更新x原链头到现链头(y链头)的距离，更新y所在列的大小。

注意每次把x合并到y后面时，x的祖先就要变成y的祖先，顺序不能反，否则会打乱维护的2、3性质。文章来源地址https://www.toymoban.com/news/detail-620912.html

/*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("-1\n");
			else printf("%d\n",abs(dis[x]-dis[y])-1);
		}
	}
	return 0;
}

到了这里，关于P1196 [NOI2002] 银河英雄传说带权并查集的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！