poj 1182-食物链【并查集】

r囧r小猫 2022-08-21 06:51 142阅读 0赞

食物链

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;59618</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;17461</td> 
  </tr> 
 </tbody> 
</table>

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

Source

[Noi 01][]

解题思路：

并查集的高级应用。

假设father\[A\]=B ，rank\[A\]=0表示A与B同类；rank\[A\]=1 表示B可以吃A；rank\[A\]=2 表示A可以吃B。

对于一组数据 d x y，若x与y的根节点相同，利用(rank\[y\]-rank\[x\]+3)%3!=d-1若不相等说明为假话；

若x与y根节点不同，说明两者不在同一集合里，进行组合。让x的根fx成为y的根fy的父节点（father\[fy\]=fx），rank\[fy\]的值需要仔细归纳得出。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int n,k;
    int per[50001];
    int vis[50001];
    int ans;
    void init()
    {
    	int i,j;
    	for(i=0;i<=n;i++)
    	{
    		per[i]=i;
    	}
    	memset(vis,0,sizeof(vis));
    }
    int find(int x)
    {
    	if(x!=per[x])
    	{
    		int cn;
    		cn=find(per[x]);
    		vis[x]=(vis[x]+vis[per[x]])%3;
    		per[x]=cn;
    	}
    	return per[x];
    }
    bool join(int x,int y,int oo)
    {
    	int fx=find(x);
    	int fy=find(y);
    	if(fx==fy)
    	{
    		 if((vis[y]-vis[x]+3)%3!=oo)return true;      
            	else return false;  
    	}
    	per[fy]=fx;
    	vis[fy]=(vis[x]-vis[y]+oo+3)%3;       
        return false; 
    }
    int main()
    {
    	scanf("%d%d",&n,&k);
    	int i,j;
    	int jj,xx,yy;
    	ans=0;
    	init();
    	for(i=0;i<k;i++)
    	{		
    		scanf("%d%d%d",&jj,&xx,&yy);
    		if(xx>n||yy>n||(xx==yy&&jj==2))
    		{
    			ans++;
    		}
    		else if(join(xx,yy,jj-1))
    		{
    			ans++;
    		}
    	}	
    	printf("%d\n",ans);
    	return 0;
    }

[Noi 01]: http://poj.org/searchproblem?field=source&key=Noi+01