題意：

Information

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 275 Accepted Submission(s): 33


Problem Description 軍情緊急，我們需要立刻開發出一個程序去處理前線偵察兵發回的情報，并做出相應的分析。現在由你負責其中的一個子模塊，你需要根據情報計算出敵方坦克的位置。
當敵方坦克靜止時，偵察兵會盡力估算出它們之間的位置，而每當敵方坦克移動時，偵察兵都會記錄下坦克新的位置并向你報告。每個坦克的位置可以由一個二維整數坐標來描述。
前線發回的情報有四種格式：
1 A B X Y
表示A坦克移動到了與B坦克的相對位置是(X,Y)的地方，即X_A = X_B + X, Y_A=Y_B+Y。
2 A X Y
表示A坦克移動到了絕對位置是(X,Y)的地方，即X_A = X, Y_A = Y。
3 A B X Y
表示發現了A坦克與B坦克的相對位置是(X,Y)，即X_A = X_B + X, Y_A=Y_B+Y。
4 A X Y
表示發現了A坦克的絕對位置是(X,Y)，即X_A = X, Y_A = Y。
我們需要你對于如下兩種詢問及時做出回應：
5 A B
表示詢問A坦克與B坦克的相對位置是多少，即分別求出X_A - X_B 以及Y_A -Y_B。
6 A
表示詢問A坦克的絕對位置是多少，即求出X_A 和Y_A。
其中A和B代表的是任意的一個坦克的編號，(X,Y)表示了坦克的二維坐標。你可以假設初始時刻我們對于敵方任何坦克的位置都一無所知，在此之后坦克的每一次移動都被偵察兵偵察到了。
請注意兩個坦克的坐標有可能相同。
Input 輸入的第一行是一個整數T（T < 1000），表示共有T組數據。
對于每組數據，第一行有一個整數N，表示這組數據有N次查詢。接下來的每行表示一次查詢，每次查詢第一個數字代表是哪種詢問，詢問的格式詳見上文。
數據范圍：
0 < N <=100000, 0<A,B<=N 且 A<>B, X和Y都是整數且 0 <=X,Y<=10000 .
測試數據中98%的數據N不超過50。
Output 對于每組數據，首先需要輸出單獨一行”Case #?:”，其中問號處應填入當前的數據組數，組數從1開始計算。
對于每一個類型(1)或者(2)的詢問，請把它們加入到你的記錄中。
對于每一個類型(3)或者(4)的詢問，如果與之前記錄的內容有矛盾，請輸出”REJECT”并將這個情報忽略掉，如沒有矛盾，請把它們加入到你的記錄中。
對于每一個類型(5)或者(6)的詢問，如果根據之前的記錄能推出結論，請輸出兩個整數X和Y，兩個整數之間有一個空格；如果不能推出結論，請輸出”UNKNOWN”。輸出的所有信息都不包括引號。
Sample Input 2 7 1 1 2 3 4 2 3 4 5 3 4 5 2 1 4 6 2 2 3 2 4 6 2 5 4 1 6 3 6 6 3 4 3 2 2 6 3 2 4 2 3 5 3 4 3 3 4 1 2
Sample Output Case #1: -9 -6 4 5 Case #2: UNKNOWN 2 2 0 -1 REJECT
思路：
? ? ? ?這個題目做了好久了，各種糾結，原因是自己吧自己繞道圈子里面了，越繞越復雜
，看到這個題目直接就想到帶權并查集，這個毫無疑問，同時還想到1,2都是創建先的節點，但關鍵是在hash節點和判斷當前這個集合時候是已知點的時候sb了，后來蒙了，當時我是標記父親節點，每次要是有個點是已知的，那么就直接吧他的當前父親節點標記上，結果各種wa，就這樣不知wa了多久，后來看了別人的處理方式，哎！真的是先想好在敲啊，思路直接敲有的時候會死的很慘的啊，對于1,2，是要建立新的節點的，其余的不用，對于已知的點，直接把他父親連接到0節點上，0節點就表示是已知的（可以是別的自己隨意），這樣寫的時候就簡單多了，對于hash點的時候，我是來一個hash一個，不來不用，具體看代碼。

#include<stdio.h>#define N 200000 int mer[N] ,X[N] ,Y[N] ,hash[N];int finds(int x) {if(x == mer[x]) return x;int t = mer[x];mer[x] = finds(mer[x]);X[x] += X[t];Y[x] += Y[t];return mer[x]; }int main () {int t ,n ,cas = 1;int key ,a ,b ,x ,y;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);printf("Case #%d:\n" ,cas ++);for(int i = 0 ;i <= n * 2 ;i ++)mer[i] = i ,X[i] = Y[i] = 0 ,hash[i] = -1;int nown = 0;hash[0] = 0;while(n--){scanf("%d" ,&key);if(key == 1 || key == 2){if(key == 1) scanf("%d %d %d %d" ,&a ,&b ,&x ,&y);else {scanf("%d %d %d" ,&a ,&x ,&y);b = 0;}hash[a] = ++nown;if(hash[b] == -1) hash[b] = ++nown;int ra = finds(hash[a]) ,rb = finds(hash[b]);mer[ra] = rb;X[ra] = X[hash[b]] - X[hash[a]] + x;Y[ra] = Y[hash[b]] - Y[hash[a]] + y;}if(key == 3 || key == 4){if(key == 3)scanf("%d %d %d %d" ,&a ,&b ,&x ,&y);else{b = 0;scanf("%d %d %d" ,&a ,&x ,&y);}if(hash[a] == -1) hash[a] = ++nown;if(hash[b] == -1) hash[b] = ++nown;int ra = finds(hash[a]) ,rb = finds(hash[b]);if(ra == rb){if(X[hash[a]] - X[hash[b]] != x || Y[hash[a]] - Y[hash[b]] != y)printf("REJECT\n");}else {mer[ra] = rb;X[ra] = X[hash[b]] - X[hash[a]] + x;Y[ra] = Y[hash[b]] - Y[hash[a]] + y;}}if(key == 5 || key == 6){if(key == 5) scanf("%d %d" ,&a ,&b);else {scanf("%d" ,&a);b = 0;}if(hash[a] == -1) hash[a] = ++nown;if(hash[b] == -1) hash[b] = ++nown;int ra = finds(hash[a]) ,rb = finds(hash[b]);if(ra != rb) printf("UNKNOWN\n");else printf("%d %d\n" ,X[hash[a]] - X[hash[b]] ,Y[hash[a]] - Y[hash[b]]);}}}return 0; }
?

總結

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

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