hdu1962Corporative Network带权回路

浏览数：18 / 时间：2015年06月09日

 1 /*
 2     有N个企业，每个企业想要实现通信，要用线路来连接，线路的长度为abs(a-b)%1000;
 3     如果企业a 链接到了企业b 那么b就是the center of the serving!
 4     然后有两种操作：
 5     E a ： 输出企业a到serving center 的线路的距离
 6     I a, b  将企业a连接到企业 b，那么b就成为了serving center（之前连接a的企业，他们的serving center也变成了b） 
 7     
 8    思路：并查集！ （压缩路径时回溯求解） ！ 
 9 */ 
10 #include<iostream>
11 #include<cstring>
12 #include<cmath>
13 #include<cstdio>
14 #define M 20005
15 using namespace std;
16 int n;
17 int f[M];
18 int ans[M];//节点 i到 serving center的距离！ 
19 
20 int getFather(int x){
21     if(x==f[x]) return x;
22     int ff=getFather(f[x]);
23     ans[x]+=ans[f[x]];//节点x到serving center 的距离要加上其父节点到serving center的距离！ 
24     return f[x]=ff;
25 }
26 
27 void Union(int a, int b){ 
28     if(a==b) return;
29     f[a]=b;
30     ans[a]=abs(a-b) % 1000;
31 }
32 
33 int main(){
34    int t;
35    char ch[3];
36    cin>>t;
37    while(t--){
38       cin>>n;
39       int a, b;
40       memset(ans, 0, sizeof(ans));
41       for(int i=1; i<=n; ++i)
42          f[i]=i;
43       while(cin>>ch && ch[0]!=‘O‘){
44           if(ch[0]==‘E‘){
45              cin>>a;
46              getFather(a);
47              cout<<ans[a]<<endl;
48           }
49           else{
50              cin>>a>>b;
51              Union(a, b);
52           }
53       }
54    }
55    return 0;
56 }