Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 64875 Accepted: 19085
Description
動物王國中有三類動物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
Source
【題解】
哎。網上有牛人寫了很完整的題解。
我復制一下。
Part I - 權值(relation)的確定。 我們根據題意,森林中有
3種動物。A吃B,B吃C,C吃A。 我們還要使用并查集,那么,我們就以動物之間的關系來作為并查集每個節點的 權值。 注意,我們不知道所給的動物(題目說了,輸入只給編號)所屬的種類。 所以,我們可以用動物之間“相對”的關系來確定一個并查集。
0 - 這個節點與它的父節點是同類
1 - 這個節點被它的父節點吃
2 - 這個節點吃它的父節點。 注意,這個
0,
1,
2所代表的意義不是隨便制定的,我們看題目中的要求。 說話的時候,第一個數字(下文中,設為d)指定了后面兩種動物的關系:
1 - X與Y同類
2 - X吃Y 我們注意到,當 d =
1的時候,( d -
1 ) =
0,也就是我們制定的意義 當 d =
2的時候,( d -
1 ) =
1,代表Y被X吃,也是我們指定的意義。 所以,這個
0,
1,
2不是隨便選的 Part II - 路徑壓縮,以及節點間關系確定 確定了權值之后,我們要確定有關的操作。 我們把所有的動物全初始化。
struct Animal {
int num;
int parent;
int relation; }; Animal ani[
50010]; 初始化為 For i =
0 to N
do ani[i].num = i; ani[i].parent = i; ani[i].relation =
0 ; End For (
1)路徑壓縮時的節點算法 我們設A,B,C動物集合如下:(為了以后便于舉例) A = {
1 ,
2 ,
3 ,
4 ,
5 } B = {
6 ,
7 ,
8 ,
9 ,
10} C = {
11,
12,
13,
14,
15} 假如我們已經有了一個集合,分別有
3個元素 SET1 = {
1,
2},我們規定集合中第一個元素為并查集的“代表” 假如現在有語句:
2 2 6 這是一句真話
2是
6的父親 ani[
6].parent =
2; ani[
6].relation =
1; 那么,
6和
1的關系如何呢? ani[
2].parent =
1; ani[
2].relation =
0; 我們可以發現
6與
2的關系是
1. 通過窮舉我們可以發現 ani[now].parent = ani[ani[now].parent].parent; ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) %
3; 這個路徑壓縮算法是正確的 關于這個路徑壓縮算法,還有一點需要注意的地方,我們一會再談 注意,根據當前節點的relation和當前節點父節點的relation推出 當前節點與其父節點的父節點的relation這個公式十分重要!! 它推不出來下面都理解不了!!自己用窮舉法推一下: 好吧,為了方便伸手黨,我給出窮舉過程 i j 爺爺 父親 兒子 兒子與爺爺
0 0 (i + j)%
3 =
0 0 1 (i + j)%
3 =
1 0 2 (i + j)%
3 =
2 1 0 (i + j)%
3 =
1 1 1 (i + j)%
3 =
2 1 2 (i + j)%
3 =
0 2 0 (i + j)%
3 =
2 2 1 (i + j)%
3 =
0 2 2 (i + j)%
3 =
1 嗯,這樣可以看到,( 兒子relation + 父親relation ) %
3 = 兒子對爺爺的relation 這就是路徑壓縮的節點算法 (
2) 集合間關系的確定 在初始化的時候,我們看到,每個集合都是一個元素,就是他本身。 這時候,每個集合都是自洽的(集合中每個元素都不違反題目的規定) 注意,我們使用并查集的目的就是盡量的把路徑壓縮,使之高度盡量矮 假設我們已經有一個集合 set1 = {
1,
2,
7,
10} set2 = {
11,
4,
8,
13},每個編號所屬的物種見上文 set3 = {
12,
5,
4,
9} 現在有一句話
2 13 2 這是一句真話,X =
13,Y =
2 我們要把這兩個集合合并成一個集合。 直接
int a = findParent(ani[X]);
int b = findParent(ani[Y]); ani[b].parent = a; 就是把Y所在集合的根節點的父親設置成X所在集合的根節點。 但是,但是!!!! Y所在集合的根結點與X所在集合的根節點的關系!!!要怎么確定呢? 我們設X,Y集合都是路徑壓縮過的,高度只有
2層 我們先給出計算的公式 ani[b].relation = (
3 - ani[Y].relation + ( d -
1 ) + ani[X].relation) %
3; 這個公式,是分三部分,這么推出來的 第一部分,好理解的一部分: ( d -
1 ) :這是X和Y之間的relation,X是Y的父節點時,Y的relation就是這個
3 - ani[Y].relation = 根據Y與根節點的關系,逆推根節點與Y的關系 這部分也是窮舉法推出來的,我們舉例: j 子 父相對于子的relation(即假如子是父的父節點,那么父的relation應該是什么,因為父現在是根節點,所以父.relation =
0,我們只能根據父的子節點反推子跟父節點的關系)
0 (
3 -
0 ) %
3 =
0 1(父吃子) (
3 -
1 ) %
3 =
2 2(子吃父) (
3 -
2 ) %
3 =
1 —————————————————————————————————————————————————————— 我們的過程是這樣的: 把ani[Y],先連接到ani[X]上,再把ani[Y]的根節點移動到ani[X]上,最后,把ani[Y]的根節點移動到ani[X]的根節點上,這樣算relation的 還記得么,如果我們有一個集合,壓縮路徑的時候父子關系是這么確定的 ani[爺爺].relation = ( ani[父親].relation + ani[兒子].relation ) %
3 我們已知道,( d -
1 )就是X與Y的relation了 而 (
3 - ani[Y].relation)就是 以Y為根節點時,他的父親的relation 那么 我們假設把Y接到X上,也就說,現在X是Y的父親,Y原來的根節點現在是Y的兒子 Y的relation + ani[Y]根節點相對于ani[Y]的relation ( ( d -
1 ) + (
3 - ani[Y].relation) ) %
3 就是ani[Y]的父親節點與ani[X]的relation了! 那么,不難得到,ani[Y]的根節點與ani[X]根節點的關系是: ( ( d -
1 ) + (
3 - ani[Y].relation) + ani[X].relation ) %
3 ->應用了同余定理 注意,這個當所有集合都是初始化狀態的時候也適用哦 還是以最開頭我們給的三個集合(分別代表三個物種)為例
2 1 6 帶入公式 ani[
6].relation = ( (
2 -
1 ) + (
3 -
0 ) +
0 ) %
3 =
1 也就是,
6被
1吃 Part III - 算法正確性的證明 首先,兩個自洽的集合,合并以后仍然是自洽的 這個不難想吧,數學上有個什么對稱性定理跟他很像的。 如果理解不了,就這么想!! 當set1和set2合并之后,set2的根節點得到了自己關于set1根節點的 正確relation值,變成了set1根節點的兒子,那么 set2的所有兒子只要用 ( ani[X].relation + ani[Y].relation ) %
3就能得到自己正確的relation值了 所以說,針對不在同一集合的兩個元素的話,除非違背了(
2)和(
3),否則永遠是真的 (無論這句話說的是什么,我們都可以根據所給X,Y推出兩個子節點之間應有的關系,這個關系一確定,所有兒子的關系都可以確定) 其實所有的不同集合到最后都會被合并成一個集合的。 我們只要在一個集合中找那些假話就可以了。 首先,如何判斷
1 X Y是不是假話。
if ( X 和 Y 不在同一集合) Union(x,y,xroot,yroot,d)
else if x.relation != y.relation ->假話 其次,如何判斷
2 X Y是不是假話
if ( X 和 Y 不在同一集合) Union(x,y,xroot,yroot,d)
else (ani[y].relation +
3 - ani[x].relation ) %
3 !=
1 ->假話 這個公式是這么來的:
3 - ani[x].relation得到了根節點關于x的relation ani[y] +
3 - ani[x].relation得到了y關于x的relation 所以,只要y關于x的relation不是
1,就是y不被x吃的話,這句話肯定是假話! (
2)路徑壓縮要特別注意的一點(錯在這里,要檢討自己) 路徑壓縮的時候,記得要 先findParent,再給當前節點的relation賦值。 否則有可能因為當前節點的父節點的relation不正確而導致錯的稀里嘩啦。 例子: set1 = {
1,
2,
7,
10} set2 = {
3,
4,
8,
11} set3 = {
12,
5,
14,
9} Union(
1,
3,
1,
3,
1) Union(
3,
12,
3,
12,
2)
1 5 1 算
5的relation 如果不先更新parent的relation,算出來應該是 (
3 -
0 +
0 +
1 ) %
3 =
1,
5被
1吃,顯然不對 這里面,+
0的那個
0是指根節點
12 的relation(未更新,這里的
0是指
12與
11的relation) 如果更新完了的話,應該是 (
3 -
0 +
2 +
1 ) %
3 =
0 ,
5與
1是同一物種,對了 這里面的
2 是更新節點
12的relation(
12與
1的relation)
那里把Y接在X的根節點的下方本來應該是這樣的。
但是我們可以換個思路
變成如下的放法。
把那三個用紅下劃線標記的東西累加起來就是relation(a,b)了
知道relation(a,b)了。
令fa[b] = a;
然后再變回
知道了relation(a,b),我們可以通過lelation(a,b)在路徑壓縮的時候獲取relation(b,y);
然后是判斷是否為假話的問題。
我們需要判斷任意兩個點(a,b)的關系;
因為最后進行完路徑壓縮每個并查集都只有兩層。
要獲取relation(a,b);
就查看(relation[a]+3-relation[b])%3;
為0表示相同物種,1表示b吃a,2表示a吃b;
這樣理解(高度只有兩層)
#include <cstdio>const int MAXN =
59999;
struct node
{
int fa, relation;
};
int n, k,d,x,y,fade =
0;
node ani[MAXN];
int findfather(
int x)
{
if (ani[x].fa == x)
return x;
int olfa = ani[x].fa;ani[x].fa = findfather(ani[x].fa);ani[x].relation = (ani[x].relation + ani[olfa].relation) %
3;
return ani[x].fa;
}
int main()
{
scanf(
"%d%d", &n, &k);
for (
int i =
1; i <= n; i++){ani[i].fa = i;ani[i].relation =
0;}
for (
int i =
1; i <= k; i++){
scanf(
"%d%d%d", &d, &x, &y);
if ((x > n || y > n) || (d ==
2 && x==y)){fade++;
continue;}
int a = findfather(x);
int b = findfather(y);
if (a != b){ani[b].fa = a;ani[b].relation = (
3 - ani[y].relation + d -
1 + ani[x].relation) %
3;}
else{
int temp = (ani[y].relation +
3 - ani[x].relation) %
3;
if (d ==
1){
if (temp !=
0)fade++;}
elseif (d ==
2){
if (temp !=
1)fade++;}}}
printf(
"%d\n", fade);
return 0;
}
轉載于:https://www.cnblogs.com/AWCXV/p/7632184.html
總結
以上是生活随笔為你收集整理的【29.42%】【POJ 1182】食物链的全部內容,希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯,歡迎將生活随笔推薦給好友。