意

動物王國中有三類動物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個物種之間的關系是相對的，對稱的，所以要記錄的是動物間的關系，而非它們是什么物種。如果我們把相互間可以確定捕食關系的動物放在一個集合中，那么實際上在處理過程中我們可能會得到多個集合，同時會出現需要將兩個集合合并的情況(例如a屬于集合A，b屬于集合B，當a，b的關系確定時，集合A，B就需要合并為一個集合)，由這種動態處理集合的情況不難聯想到并查集。

利用并查集來存儲已知的捕食結構。當f[a]=a時，表示a是本集合的根結點，f[a]=b表示a，b間有已經確定的捕食關系。這樣想知道a，b間的捕食關系只要找到a，b的根結點即可，a，b有相同根結點則可通過邏輯判斷確定a，b關系，a，b有不同根節點，說明a，b關系尚未確定。這樣我們還需要一個和f[n]對應的存儲結構 vec[n]用以存儲f[a]與其父結點的捕食關系。由于關系都是相對的，而且有向的，我們可以以向量的思想來確定。

我們以vec[a]=0表示a結點與其父結點是同類，vec[a]=-1表示a捕食其父結點，vec[a]=1表示a被其父結點捕食。首先構造函數getf(a)來得到a的根結點，構造getv(a)來得到a與其根結點的關系向量。

?

當得到輸入d a b時，若ab有相同根結點，則如上圖，不難有d-1==getv(b)-getv(a)時是真話。

同樣，a，b有不同根結點時，這句話為真，可以確定兩根結點的關系，a到b的關系向量為:

?getv(b)-(d-1)-getv(a);
以上就是以向量和并查集來考慮本題的思路。

參考： http://hi.baidu.com/bobo__bai/item/fbf57d110b72650fb88a1a09

參考代碼：代碼中用pa數組表示每個節點的父節點，ch數組表示節點與它的父節點的關系，即向量的關系。

#include <stdio.h>
#include <string.h>
const int MAXN = 50005;
int pa[MAXN], ch[MAXN];
int n, k, lies;
void init_set()
{
??? int i;
??? for (i = 0; i < MAXN; i++) pa[i] = i;
??? memset(ch, 0, sizeof(int)*MAXN);
??? lies = 0;
}
?
int find_set(int x)
{
??? if (pa[x] == x)
??????? return x;
??? int xt = find_set(pa[x]);
??? ch[x] = (ch[x] + ch[pa[x]] + 3) % 3;
??? pa[x] = xt;
??? return xt;
}
void union_set(int d, int x, int y)? // d, 表示 x 對 y 的關系，0， 同類，1，x吃y
{
??? if (x > n || y > n )? {
??????? ++lies;
??????? return;
??? }
??? int fx = find_set(x);
??? int fy = find_set(y);
??? if (fx == fy)? {
??????? if ((ch[x] - ch[y] + 3) % 3 != d) {
??????????? ++lies;
??????? }
??? } else {
??? ?ch[fx] = (d + ch[y] - ch[x] + 6) % 3;
pa[fx] = fy;
}
}
int main()
{
??? int i, d, x, y;
??? scanf("%d %d\n", &n, &k);
??? init_set();
??? for (i = 0; i < k; i++) {
??????? scanf("%d %d %d\n", &d, &x, &y);
??????? union_set(d - 1, x, y);
??? }
??? printf("%d", lies);
??? return 0;
}

轉載于:https://www.cnblogs.com/13224ACMer/p/4434801.html

總結

以上是生活随笔為你收集整理的poj1182(食物链）续的全部內容，希望文章能夠幫你解決所遇到的問題。

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