hdu1962Corporative Network带权回路-白红宇

有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) % 1000;

}

int main(){

int t;

char ch[3];

cin>>t;

while(t--){

cin>>n;

int a, b;

memset(ans, 0, sizeof(ans));

for(int i=1; i<=n; ++i)

f[i]=i;

while(cin>>ch && ch[0]!='O'){

if(ch[0]=='E'){

cin>>a;

getFather(a);

cout<<ans[a]<<endl;

}

else{

cin>>a>>b;

Union(a, b);

}

return 0;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3902548.html，如需转载请自行联系原作者