POJ3678KatuPuzzle(2

POJ 3678 Katu Puzzle(2-SAT) http://poj.org/problem?id=3678 题意: 一个N个顶点和M条边的有向图,每个顶点能取0或1两个.现在每条边被一个操作符(or,and,xor)以及一个(0或1)标记了,表示a与b按操作符运算的结果是(0或1).问你该有向图是否有可行解? 分析: 由于

POJ 3678 Katu Puzzle(2-SAT)

http://poj.org/problem?id=3678

题意:

一个N个顶点和M条边的有向图,每个顶点能取0或1两个值.现在每条边被一个操作符(or,and,xor)以及一个值(0或1)标记了,表示a与b按操作符运算的结果是值(0或1).问你该有向图是否有可行解?

分析:

由于每个点只能取0或1两个值,所以我们把该问题转化为2-SAT问题.原图中的每个点对应2-SAT中的每个点.对于每种运算有下列转换方式:

a and b = 0 转换为 a=0 或 b=0

a and b = 1 转换为 a=1 且 b=1 即添加边 2*a->2*a+1 2*b->2*b+1(只要a为0或b为0必然引起矛盾)

a or b = 0 转换为 2*a+1->2*a 2*b+1->2*b(只要a为1或b为1必然引起矛盾)

a or b = 1 转换为 a=1 或b=1

a xorb=0转换为 a=1且b=1 或 a=0且b=0 即连下面的边:

2*a->2*b 2*b->2*a 2*a+1->2*b+1 2*b+1->2*a+1.

a xor b=1 转换为a=1且b=0 或a=0且b=1 则连下面的边:

2*a+1->2*b 2*b->2*a+1 2*a->2*b+1 2*b+1->2*a

AC代码:

#include
#include
#include
#include
using namespace std;
const int maxn=1000+10;
struct TwoSAT
{
 int n;
 vector G[maxn*2];
 int S[maxn*2],c;
 bool mark[maxn*2];

 bool dfs(int x)
 {
 if(mark[x^1]) return false;
 if(mark[x]) return true;
 mark[x]=true;
 S[c++]=x;
 for(int i=0;in=n;
 for(int i=0;i0) mark[S[--c]]=false;
 if(!dfs(i+1)) return false;
 }
 }
 return true;
 }
}TS;
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 TS.init(n);
 int a,b,c;
 char op[10];
 for(int i=0;i