原題傳送：http://poj.org/problem?id=1988

　　一開始的想法是把下堆連到上堆去（這很符合樹的結構思想），然后另外開一個數組標記錄節點的值，遞歸的時候字節點加上這個標記的值與根節點的差值，但是發現，這樣做在某些union_set時會使同一個根的所有節點標記的值錯亂。

　　這道題需要對并查集有比較深刻的理解，多開一個數組記錄堆總數。把上堆union到下堆上去，這樣，總的根就是下堆的根，最上堆總是在最下層，find_set的時候就很方便求出答案。

View Code 1 #include <stdio.h> 2 #define N 30001 3 4 int a[N], f[N], num[N], v[N]; 5 6 int find_set(int x) 7 { 8 if(x != f[x]) 9 { 10 int tmp = f[x]; 11 f[x] = find_set(f[x]); 12 num[x] += num[tmp]; 13 } 14 return f[x]; 15 } 16 17 void union_set(int a, int b) 18 { 19 int x = find_set(a); 20 int y = find_set(b); 21 if(x != y) 22 { 23 f[x] = y; 24 num[x] += v[y]; 25 v[y] += v[x]; 26 } 27 } 28 29 void make_set() 30 { 31 for(int i = 0; i < N; i ++) 32 f[i] = i, num[i] = 0, v[i] = 1; 33 } 34 35 int main() 36 { 37 int p, a, b; 38 char op[5]; 39 make_set(); 40 scanf("%d", &p); 41 while(p --) 42 { 43 scanf("%s", op); 44 if(op[0] == 'M') 45 { 46 scanf("%d%d", &a, &b); 47 union_set(a, b); 48 } 49 else 50 { 51 scanf("%d", &a); 52 find_set(a); 53 printf("%d\n", num[a]); 54 } 55 } 56 return 0; 57 }

轉載于:https://www.cnblogs.com/huangfeihome/archive/2012/09/12/2682344.html

總結

以上是生活随笔為你收集整理的POJ1988 Cube Stacking的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。