Poj1182食物链

Posted by yjjr's blog on February 6, 2018

POJ1182食物链

标签:并查集

http://www.sakurasake.icoc.me/nd.jsp?id=3#_np=2_327

Time Limit: 1000MS


Memory Limit: 10000K

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

Noi 01

 

分析:用动物之间的关系来确定并查集

设f[x]表示x的根节点,rank[x]表示f[x]与x的关系

Rank[x]==0表示f[x]与x同类,rank[x]==1表示f[x]吃x,rank[x]==2表示x吃f[x]

假设已读入d,x,y

先利用find()函数得到x,y分别的根节点root1,root2

1.     若d==1&&rank[x]!=rank[y]那么这句话为假

因为d==1表示x与y为同类,而rank[x]!=rank[y]可以推出不同类,矛盾

2.     若d==2&&rank[x]==rank[y](或者rank[x]==(rank[y]+1)%3)那么此话为假

因为d==2表示x吃y,即不同类,而rank[x]==rank[y]可以推出同类,矛盾

假设有y吃x,那么rank[x]与rank[y]的值会有那些可能??

列举如下:

Rank[x]==0&&rank[y]==2;

Rank[x]==1&&rank[y]==0;

Rank[x]==2&&rank[y]==1;

简单观察发现rank[x]=(rank[y]+1)%3;

敲黑板!!重点来了!!!

对于上个问题有个更一般的判断方法:

若(rank[y]-rank[x]+3)%3!=d-1,那么此话为假。

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<bitset>
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
using namespace std;
int f[50005];
int rank[50005];

int find(int x)
{
	int t;
	if(x==f[x])return x;
	else 
	{
		t=f[x];
		f[x]=find(f[x]);//路径压缩
		rank[x]=(rank[x]+rank[t])%3;
		return f[x];
	}
}

int main()
{
	int total=0;
	int i,n,k,x,y,d,root1,root2;
	n=read();k=read();
	for(i=1;i<=n;i++){f[i]=i;rank[i]=0;}//初始化
	while(k--)
	{
		d=read();x=read();y=read();
		if(x>n||y>n||(d==2&&x==y))total++;//根据题意初步判断
		else{
			root1=find(x);root2=find(y);
			if(root1==root2)
			{
				if((rank[x]-rank[y]+3)%3!=d-1)total++;
			}
			else 
			{
				f[root1]=root2;
				rank[root1]=(rank[y]-rank[x]+3+d-1)%3;
			}//合并x,y
		}
	}
	cout<<total<<endl;
	return 0;
}




本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr