題意:
? ? ? 動物王國中有三類動物A,B,C，這三類動物的食物鏈構成了有趣的環形。A吃B， B吃C，C吃A。?
現有N個動物，以1－N編號。每個動物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。?
有人用兩種說法對這N個動物所構成的食物鏈關系進行描述：?
第一種說法是"1 X Y"，表示X和Y是同類。?
第二種說法是"2 X Y"，表示X吃Y。?
此人對N個動物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。?
1） 當前的話與前面的某些真的話沖突，就是假話；?
2） 當前的話中X或Y比N大，就是假話；?
3） 當前的話表示X吃X，就是假話。?
你的任務是根據給定的N（1 <= N <= 50,000）和K句話（0 <= K <= 100,000），輸出假話的總數。?
Input


第一行是兩個整數N和K，以一個空格分隔。?
以下K行每行是三個正整數 D，X，Y，兩數之間用一個空格隔開，其中D表示說法的種類。?
若D=1，則表示X和Y是同類。?
若D=2，則表示X吃Y。
Output


只有一個整數，表示假話的數目。
Sample Input


100 7
1 101 1?
2 1 2
2 2 3?
2 3 3?
1 1 3?
2 3 1?
1 5 5
Sample Output


3

思路:

? ? ? 很直白的帶權并查集,今年攜程第二場的第一題也是這個,我知道的帶權有三種,一個是距離遠點的距離,一個是搬家次數,一個是集合元素個數,這個事距離遠點的距離,但是有個要求,就是距離永遠%3,因為只有三種動物,水題,直接上代碼了...

#include<stdio.h> #include<string.h>#define N 50000 + 500int mer[N]; int s_x[N];int finds(int x) {if(mer[x] == x) return x;int k = mer[x];mer[x] = finds(mer[x]);s_x[x] += s_x[k];s_x[x] %= 3;return mer[x]; }int main () {int n ,m ,k ,a, b;int ans ,i;scanf("%d %d" ,&n ,&m);for(i = 1 ;i <= n ;i ++)mer[i] = i ,s_x[i] = 0;ans = 0;for(i = 1 ;i <= m ;i ++){scanf("%d %d %d" ,&k ,&a ,&b);if(a >n || b > n){ans ++;continue;}int x = finds(a);int y = finds(b);if(k == 1){if(x == y){if(s_x[a] != s_x[b])ans ++;}else{mer[y] = x;s_x[y] = (s_x[a] - s_x[b] + 3) % 3;}}else{if(x == y){if((s_x[a] + 1) % 3 != s_x[b])ans ++;}else {mer[y] = x;s_x[y] = (s_x[a] - s_x[b] + 3 + 1) % 3;}}}printf("%d\n" ,ans);return 0; }

總結

以上是生活随笔為你收集整理的poj1182 and 携程预赛2第一题 带权并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

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