题解 P1196 【[NOI2002]银河英雄传说】

2018-04-22 11:35:24


解法一:首先想到的方法当然是直接模拟,用并查集模拟每一合并。

但是求路径距离不方便,要暴力

时间复杂度呈指数增长

只能的20

QAQ

解法2:

正解是利用 带权的并查集

所谓的带权,指的是不仅可以查看是否在某一个集合中,还可以看点到根的距离


你会想 那可不可以路径压缩?如果要压缩,那么就无法判断点到顶点的距离


其实是可以的

在压缩的时候顺便把路径长度保存在另外的一个数组里


int find(int now){
    if(now!=fa[now]){
        int father=fa[now];
        fa[now]=find(fa[now]);
        w[now]+=w[father];
    }
    return fa[now];
}

下面上本蒟蒻丑陋代码

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