題意：
? ? ? ?可以這樣理解，有n快方形積木，一開始都是單獨的放到哪，然后有兩種操作
1 M a b 把a所在的那一堆落到b所在那一堆的上面(一開始自己是一堆)
2 C a 問a下面有多少個積木


思路：?
? ? ? ?感覺很久以前杭電上見過這個題目，比較簡單的帶權并查集，我們可以維護兩個權來滿足要求，第一個就是記錄集合元素個數，就是合并的時候更新a所在的祖宗節點的距離權值，第二個權值就是距離權值，記錄每個元素距離根節點的距離，然后更新就是簡單更新沒啥說的，還有就是簡簡單單敲完提交后WA了一發，哎！丟臉，還好不是比賽，讓我想起了有一場亞洲賽的水題我果斷敲完，然后上去1WA。這個題目我WA是因為忘記了輸出距離權值前要先查詢一下，也就是更新一下，因為用了路徑壓縮，路徑壓縮的最理想狀態是一個點，四周連著所有本集合的其他點，但是要想把一個路徑上壓縮成一對多，起碼要查詢就是更新一便，因為在動態的更新的時候當前所有狀態并是不理想路徑壓縮后的狀態，這個自己畫畫很容易理解，哎！記得當時還經常給小學弟講這個問題呢！。


#include<stdio.h>


#define N 30000 + 10


int mer[N] ,sum[N] ,s_x[N];


int Finds(int x)
{
? ? if(x == mer[x]) return x;
? ? int t = mer[x];
? ? mer[x] = Finds(mer[x]);
? ? s_x[x] += s_x[t];
? ? return mer[x];
}


int main ()
{
? ? int m ,i ,x ,y ,a ,b;
? ? char str[5];
? ? for(i = 1 ;i <= 30000 ;i ++)
? ? s_x[i] = 0 ,sum[i] = 1 ,mer[i] = i;
? ? scanf("%d" ,&m);
? ? for(i = 1 ;i <= m ;i ++)
? ? {
? ? ? ? scanf("%s" ,str);
? ? ? ? if(str[0] == 'M')
? ? ? ? {
? ? ? ? ? ? scanf("%d %d" ,&a ,&b);
? ? ? ? ? ? x = Finds(a);
? ? ? ? ? ? y = Finds(b);
? ? ? ? ? ? s_x[x] = sum[y];
? ? ? ? ? ? sum[y] += sum[x];
? ? ? ? ? ? mer[x] = y;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&a);
? ? ? ? ? ? Finds(a);
? ? ? ? ? ? printf("%d\n" ,s_x[a]);
? ? ? ? }
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ1988（带权并查集，搬砖块）的全部內容，希望文章能夠幫你解決所遇到的問題。

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