POJ--3678[Katu Puzzle] 第三道2-SAT

題目大意：

一些點，點的取值可以是0或者1，沒有告訴你具體取值。

一些邊，有權值，有運算方式（并，或，異或），要求和這條邊相連的兩個點經過邊上的運算後的結果是邊的權值。

問你有沒有可能把每個點指派滿足所有邊的要求。

思路分析：

每個點隻有0，1兩種值，并且和邊對面的點有限制條件，是以可以轉化為2-sat問題。

令i表示點i取1，i + n表示點i取0.

關鍵：

(1):and 等于 1時，要求i和j必須為1，不能為0.

不能為0的處理時：如果i取0，那麼i就要取1.

即：i + n -> i。

(2):or 等于 0時，要求i和j必須為0，不能為1.

不能為1的處理時：如果i取1，那麼i就要取0.

即：i -> i + n。

CODE:

/*POJ2-SAT第三題*/
/*關鍵處理：不能為0和不能為1的處理*/
/*AC代碼：94ms*/
#include <iostream>
#define MAXN 4005
struct edge
{
	int v,next;
	edge(){}
	edge(int v1,int next1)
	{v=v1;next=next1;}
}E[4000005];
int head[MAXN],ecnt;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];
bool Instack[MAXN];
int Index,cnt,top,N,M;
void Insert(int u,int v)
{
	E[ecnt]=edge(v,head[u]);
	head[u]=ecnt++; 
}
void Tarjan(int u)
{
	int v,i;
	Low[u]=DFN[u]=++Index;
	Instack[u]=true;
	Stack[++top]=u;
	for(i=head[u];i!=-1;i=E[i].next)
	{
		v=E[i].v;
		if(!DFN[v])
		{
			Tarjan(v);
			if(Low[u]>Low[v])
				Low[u]=Low[v];
		}
		else if(Instack[v]&&Low[u]>DFN[v])
			Low[u]=DFN[v];
	}
	if(Low[u]==DFN[u])
	{
		cnt++;
		do{
			v=Stack[top--];
			Instack[v]=false;
			Belong[v]=cnt;
		}while(u!=v);
	}
	return;
}
void Build_Map()
{
	int i,u,v,c;
	char s[5];
	for(i=0;i<M;i++)
	{
		scanf("%d%d%d%s",&u,&v,&c,s);
		if(s[0]=='A')
		{
			if(c==1)
			{
				Insert(u+N,u);//不能為0的處理
				Insert(v+N,v);
				//Insert(u,v);
				//Insert(v,u);
			}
			else
			{
				Insert(u,v+N);
				Insert(v,u+N);
			}
		}
		else if(s[0]=='O')
		{
			if(c==1)
			{
				Insert(u+N,v);
				Insert(v+N,u);
			}
			else
			{
				Insert(u,u+N);//不能為1的處理
				Insert(v,v+N);
				//Insert(u+N,v+N);
				//Insert(v+N,u+N);
			}
		}
		else
		{
			if(c==1)
			{
				Insert(u,v+N);
				Insert(v+N,u);
				Insert(v,u+N);
				Insert(u+N,v);
			}
			else
			{
				Insert(v,u);
				Insert(u,v);
				Insert(v+N,u+N);
				Insert(u+N,v+N);
			}
		}
	}
}
bool Sat()
{
	int i;
	memset(Instack,false,sizeof(Instack));
	memset(DFN,0,sizeof(DFN));
	memset(Low,0,sizeof(Low));
	Index=cnt=top=0;
	for(i=0;i<2*N;i++)
	{if(!DFN[i]) Tarjan(i);}
	for(i=0;i<N;i++)
		if(Belong[i]==Belong[i+N])
			return false;
		return true;
}
int main()
{
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		ecnt=0;
		memset(head,-1,sizeof(head));
		Build_Map();
		if(Sat()) printf("YES\n");
		else printf("NO\n"); 
	}
	return 0;
}