题解 P1196 【[NOI2002]银河英雄传说】
vivarock
2018-04-22 11:35:24
解法一:首先想到的方法当然是直接模拟,用并查集模拟每一合并。
但是求路径距离不方便,要暴力
时间复杂度呈指数增长
只能的20
~~QAQ~~
解法2:
### 正解是利用 带权的并查集
所谓的带权,指的是不仅可以查看是否在某一个集合中,还可以看点到根的距离
------------
你会想 那可不可以路径压缩?如果要压缩,那么就无法判断点到顶点的距离
------------
其实是可以的
在压缩的时候顺便把路径长度保存在另外的一个数组里
------------
```cpp
int find(int now){
if(now!=fa[now]){
int father=fa[now];
fa[now]=find(fa[now]);
w[now]+=w[father];
}
return fa[now];
}
```
------------
下面上本蒟蒻丑陋代码
```cpp
#include<bits/stdc++.h>//万能大法好
using namespace std;
#define maxn 30010//宏定义
int w[maxn],fa[maxn],num[maxn],n;
//w表示从自己到根的距离,num表示以i为根的并查集的元素个数,fa表示根
int find(int now){
if(now!=fa[now]){
int father=fa[now];
fa[now]=find(fa[now]);
w[now]+=w[father];
}
return fa[now];
}
//查找+路径压缩
#define For(i,j,n) for(int i=(j);i<=(n);++i)
void merge(int a,int b){
int x=find(a),y=find(b);
w[x]+=num[y];
fa[x]=y;
num[y]+=num[x];
num[x]=0;
}
//合并
int main(){
For(i,1,maxn)fa[i]=i,num[i]=1;
//初始化
cin>>n;
For(i,1,n){
char a;int b,c;
cin>>a>>b>>c;
if(a=='M')merge(b,c);
else if(find(b)==find(c))printf("%d\n",abs(w[b]-w[c])-1);//两个点间的距离可以用abs(w[b]-w[c])-1表示,应为重复b点,所以减去1
else printf("-1\n");
}
return 0;
}
```