[並查集]NOI2001 食物鏈 eat 解題報告

Title: 食物链    題目連結：COGS

Input: eat.in

Output: eat.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★★☆

动物王国中有三类动物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），输出假话的总数。

输入文件
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

• 若D=1，则表示X和Y是同类。
• 若D=2，则表示X吃Y。

输出文件
只有一个整数，表示假话的数目。
输入样例
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输入文件

输出样例

3
样例说明
对7句话的分析

• 1 101 1 假话
• 2 1 2 真话
• 2 2 3 真话
• 2 3 3 假话
• 1 1 3 假话
• 2 3 1 真话
• 1 5 5 真话

「分析」

本題是並查集的經典應用。
每次判斷時，前兩個條件都能O（1）判斷，關鍵在於第3個條件。
由於無法判斷可以另外虛設2*N個物種，分別表示能吃第i個物種的物種和被第i個物種所吃的物種。那麼剩下就是裸並查集了，每次合併就把那個三角環依次合併即可。

「我的代碼」

 

C++语言: Codee#24995

001 /*
002 *Problem: NOI2001-eat
003 *Author: Yee-fan Zhu
004 *Time: Jan 02,2012
005 *Method: UFS
006 */
007 #include <iostream>
008 #include <cstdlib>
009 #include <cstdio>
010 using namespace std;
011 const int MAX=150010;
012
013 int N,K;
014 int Ani[MAX];
015 int Eat[MAX];
016 int Eaten[MAX];
017 int False=0;
018
019 int UFS_Find(int x)
020 {
021     int t,p;
022     p=x;
023     while(Ani[p]!=p)
024         p=Ani[p];
025     while(Ani[x]!=x)  //Compress Path
026     {
027         t=Ani[x];
028         Ani[x]=p;
029         x=t;
030     }
031     return p;
032 }
033
034 bool UFS_Check(int a,int b)
035 {
036     int x=UFS_Find(a);
037     int y=UFS_Find(b);
038     return (x==y);
039 }
040
041 void UFS_Merge(int a,int b)
042 {
043     Ani[UFS_Find(b)]=UFS_Find(a);
044 }
045
046 void init()
047 {
048     scanf("%d %d\n",&N,&K);
049     for (int i=1;i<=N;i++)
050     {
051         int x=N+i;
052         int y=N*2+i;
053         Ani[i]=i,Ani[x]=x,Ani[y]=y;
054         Eaten[i]=x,Eat[i]=y;
055         Eaten[x]=y,Eat[x]=i;
056         Eaten[y]=i,Eat[y]=x;
057     }
058 }
059
060 void work()
061 {
062     int D,X,Y;
063     for (int i=1;i<=K;i++)
064     {
065         scanf("%d %d %d\n",&D,&X,&Y);
066         if(X>N || Y>N)
067         {
068             False++;
069             continue;
070         }
071         if(D==2 && X==Y)
072         {
073             False++;
074             continue;
075         }
076
077         if(D==1)
078         {
079             if(UFS_Check(X,Y))
080                 continue;
081             if(UFS_Check(Eat[X],Y) ||  UFS_Check(Eaten[X],Y) )
082             {
083                 False++;
084                 continue;
085             }
086
087             UFS_Merge(X,Y);
088             UFS_Merge(Eaten[X],Eaten[Y]);
089             UFS_Merge(Eat[X],Eat[Y]);
090             continue;
091         }
092
093         if(D==2)
094         {
095             if(UFS_Check(Eat[X],Y))
096                 continue;
097
098             if(UFS_Check(X,Y) || UFS_Check(Eaten[X],Y))
099             {
100                 False++;
101                 continue;
102             }
103
104             UFS_Merge(Eat[X],Y);
105             UFS_Merge(X,Eaten[Y]);
106             UFS_Merge(Eaten[X],Eat[Y]);
107             continue;
108         }
109     }
110 }
111
112 int main()
113 {
114     freopen("eat.in","r",stdin);
115     freopen("eat.out","w",stdout);
116     init();
117     work();
118     printf("%d\n",False);
119     return 0;
120 }