POJ 3678 2-sat裸题

题意：

给定n个未知数（每个未知数从0-n-1标号，每个数的解为true 或 false）m个等式。

下面m行

u v d & 表示 u & v = d

问： n个未知数是否有解

2-sat裸题，直接建边即可。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<math.h>
#include<iostream>
using namespace std;

#define N 1005*2
#define M 1000005
//注意n是拆点后的大小 即 n <<= 1 N为点数(注意要翻倍) M为边数
struct Edge{
	int to, nex;
}edge[M];
//注意 N M 要修改
int head[N], edgenum;
void addedge(int u, int v){
	Edge E = {v, head[u]};
	edge[edgenum] = E;
	head[u] = edgenum ++;
}

bool mark[N];
int Stack[N], top;
void init(){
	memset(head, -1, sizeof(head)); edgenum = 0;
	memset(mark, 0, sizeof(mark));
}

bool dfs(int x){
	if(mark[x^1])return false;//一定是拆点的点先判断
	if(mark[x])return true;

	mark[x] = true;
	Stack[top++] = x;

	for(int i = head[x]; i != -1; i = edge[i].nex)
		if(!dfs(edge[i].to)) return false;

	return true;
}

bool solve(int n){
	for(int i = 0; i < n; i+=2)
		if(!mark[i] && !mark[i^1])
		{
			top = 0;
			if(!dfs(i))
			{
				while( top ) mark[ Stack[--top] ] = false;
				if(!dfs(i^1)) return false;
			}
		}
	return true;
}

int main(){
	int n, m, u, v, d;
	while(~scanf("%d %d",&n,&m)){
		n<<=1;
		init();
		while(m--)
		{
			char s[10];
			scanf("%d %d %d %s",&u,&v,&d,s);
			if(s[0] == ‘A‘)
			{
				if(d)
				{
					addedge(u<<1, v<<1);
					addedge(v<<1, u<<1);
					addedge(u<<1|1, u<<1);
					addedge(v<<1|1, v<<1);
				}
				else {
					addedge(u<<1, v<<1|1);
					addedge(v<<1, u<<1|1);
				}
			}
			if(s[0] == ‘O‘)
			{
				if(d){
					addedge(u<<1|1, v<<1);
					addedge(v<<1|1, u<<1);
				}
				else 
				{
					addedge(u<<1, u<<1|1);
					addedge(v<<1, v<<1|1);
					addedge(u<<1|1, v<<1|1);
					addedge(v<<1|1, u<<1|1);
				}
			}
			if(s[0] == ‘X‘)
			{
				if(d)
				{
					addedge(u<<1, v<<1|1);
					addedge(u<<1|1, v<<1);
					addedge(v<<1, u<<1|1);
					addedge(v<<1|1, u<<1);
				}
				else
				{
					addedge(u<<1, v<<1);
					addedge(u<<1|1, v<<1|1);
					addedge(v<<1, u<<1);
					addedge(v<<1|1, u<<1|1);
				}
			}
		}
		solve(n)?puts("YES") : puts("NO");
	}
	return 0;
}
/*
4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

*/

POJ 3678 2-sat裸题

原文：http://blog.csdn.net/acmmmm/article/details/18740541