LA 3027 Corporative Network

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

这题感觉和 POJ 1988 Cube Stacking 很像，在路径压缩的同时递归出来的时候跟新distant数组

 1 //#define LOCAL
 2 #include <algorithm>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int maxn = 20000 + 10;
 7 int parent[maxn], distant[maxn];
 8 
 9 int GetParent(int a)
10 {
11     if(parent[a] == a)    return a;
12     int root = GetParent(parent[a]);
13     distant[a] += distant[parent[a]];
14     return parent[a] = root;
15 }
16 
17 int main(void)
18 {
19     #ifdef LOCAL
20         freopen("3027in.txt", "r", stdin);
21     #endif
22 
23     int T, n;
24     scanf("%d", &T);
25     while(T--)
26     {
27         scanf("%d", &n);
28         for(int i = 1; i <= n; ++i)
29         {
30             parent[i] = i;
31             distant[i] = 0;
32         }
33         getchar();
34         char p;
35         while(scanf("%c", &p) == 1 && p != ‘0‘)
36         {
37             int a, b;
38             if(p == ‘E‘)
39             {
40                 scanf("%d", &a);
41                 GetParent(a);
42                 printf("%d\n", distant[a]);
43             }
44             else
45             {
46                 scanf("%d%d", &a, &b);
47                 parent[a] = b;
48                 distant[a] = abs(a - b) % 1000;
49             }
50             getchar();
51         }
52     }
53     return 0;
54 }