hdu1962Corporative Network带权回路

时间:2023-11-25 19:46:08
 /*
有N个企业,每个企业想要实现通信,要用线路来连接,线路的长度为abs(a-b)%1000;
如果企业a 链接到了企业b 那么b就是the center of the serving!
然后有两种操作:
E a : 输出企业a到serving center 的线路的距离
I a, b 将企业a连接到企业 b,那么b就成为了serving center(之前连接a的企业,他们的serving center也变成了b) 思路:并查集! (压缩路径时回溯求解) !
*/
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define M 20005
using namespace std;
int n;
int f[M];
int ans[M];//节点 i到 serving center的距离! int getFather(int x){
if(x==f[x]) return x;
int ff=getFather(f[x]);
ans[x]+=ans[f[x]];//节点x到serving center 的距离要加上其父节点到serving center的距离!
return f[x]=ff;
} void Union(int a, int b){
if(a==b) return;
f[a]=b;
ans[a]=abs(a-b) % ;
} int main(){
int t;
char ch[];
cin>>t;
while(t--){
cin>>n;
int a, b;
memset(ans, , sizeof(ans));
for(int i=; i<=n; ++i)
f[i]=i;
while(cin>>ch && ch[]!='O'){
if(ch[]=='E'){
cin>>a;
getFather(a);
cout<<ans[a]<<endl;
}
else{
cin>>a>>b;
Union(a, b);
}
}
}
return ;
}