LA 3027 Corporative Network
这题感觉和 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 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。