3A头条

P1196 [NOI2002] 银河英雄传说 带权并查集

2023-08-01 14:50 由 makerY 发表于 #其他

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<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;
}

热门相关：洪荒二郎传   神算大小姐   修真界败类   神算大小姐   3位娃娃脸韩国新人首次亮相