【ybtoj】银河英雄传说

本文主要是介绍【ybtoj】银河英雄传说，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【ybtoj】银河英雄传说

---

题目描述

解题思路

这是带边权的并查集。用并查集维护战舰是否在同一列，以每一列的第一艘战舰作为集合代表，用一个dis数组记录边权。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, x, y, xx, yy, fa[50010], num[50010], dis[50010];
char c;
int find(int x) 
{if(fa[x]==x)return x;int cnt=find(fa[x]);dis[x]=dis[fa[x]]+dis[x];fa[x]=cnt;return fa[x];
}
int main() 
{for(int i=1;i<=50000;i++)fa[i]=i,num[i]=1;scanf("%d",&n);for(int i=1;i<=n;i++) {cin>>c;scanf("%d %d",&x,&y);xx=find(x),yy=find(y);if (c== 'M') {fa[xx]=yy;dis[xx]=num[yy];num[yy]+=num[xx],num[xx]=0;} else {if(xx!=yy)printf("-1\n");elseprintf("%d\n",abs(dis[x]-dis[y])-1);}}
}

---

谢谢阅读

这篇关于【ybtoj】银河英雄传说的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---