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

解法一：首先想到的方法当然是直接模拟，用并查集模拟每一合并。 但是求路径距离不方便，要暴力 时间复杂度呈指数增长 只能的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; } ```