本文主要是介绍P1196 [NOI2002] 银河英雄传说 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目传送门
分析
可以看到，题目中涉及到很多合并和查询操作，所以我们可以用并查集来维护每列的信息。
不过这题需要而外维护两个数组 d i s i dis_i disi 和 s i z i siz_i sizi，分别表示距离序列头部的距离和以 i i i 做头的序列长度。
合并时需要更新 s i z siz siz 和 d i s dis dis。
查询 i i i 和 j j j 之间的飞船个数就是 ∣ d i s i − d i s j ∣ − 1 |dis_i-dis_j|-1 ∣disi−disj∣−1。
代码
#include <bits/stdc++.h>
using namespace std;
int t;
int fa[30005];
int dis[30005];
int siz[30005];
int find(int x){if(fa[x]==x)return x;int f=find(fa[x]);dis[x]+=dis[fa[x]];return fa[x]=f;
}
void merge(int i,int j){int x=find(i),y=find(j);if(x!=y){dis[x]+=siz[y];fa[x]=y;siz[y]+=siz[x];siz[x]=0;}
}int main(){cin>>t;for(int i=1;i<=30000;i++)fa[i]=i,dis[i]=0,siz[i]=1;while(t--){char ch;int i,j;cin>>ch>>i>>j;if(ch=='M'){merge(i,j);}else{if(find(i)!=find(j))cout<<-1<<endl;else cout<<abs(dis[i]-dis[j])-1<<endl;}}system("pause");return 0;
}
这篇关于P1196 [NOI2002] 银河英雄传说 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
