首页 > 代码库 > POJ 3678 Katu Puzzle（2-sat 模板题）
POJ 3678 Katu Puzzle（2-sat 模板题）
题目链接：http://poj.org/problem?id=3678
Description
Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:
Xa op Xb = c
The calculating rules are:
|
|
|
Given a Katu Puzzle, your task is to determine whether it is solvable.
Input
The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.
Output
Output a line containing "YES" or "NO".
Sample Input
4 4 0 1 1 AND 1 2 1 OR 3 2 0 AND 3 0 0 XOR
Sample Output
YES
Hint
Source
大牛思路：
由于集合中的每个元素只有两种选择，要么为0，要么为1，所以可以将这个问题转化成一个2-sat判定问题。对于集合中的每个元素，看做两个点:i和i+n。i表示这个元素取0，i+n表示这个元素取1。那么，剩下的问题就是如何构图了。
首先，理解清楚求解2-sat的方法是很必要的。求解2-sat的方法是，构造出一个图，图中的有向边<x,y>表示选x时必须选y。只有这个图满足这个条件，并且所有的边都是对称的（假如原问题能转化成2-sat判定，那么图中的边必然是对称的），那么就可以利用求强连通分量缩点的方法来验证2-sat问题。
对于本题，我们逐个考虑每个逻辑运算：
1、A AND B=0.这要求A和B不同时为1。既然不同时为1，那么A取1时，B必须取0；B取1时，A必须取0.所以，要连得边便是A+n->B, B+n->A。
2、A AND B=1.这要求A和B同时为1。换句话说，A和B不能是0.那要怎么样体现在图中呢？我们知道，判断一个2-sat问题是否存在合法方案的方法是，缩点后判断有没有两个同组点属于同一个连通分量。我们需要A和B都必须是1，那么我们就让A和B必须选0时无解即可。也就是说，连边A->A+n, B->B+n。这样的话，假如构图完成后，A必须取0，那么由于存在边A->A+n，所以A也必须取1，那么就不可能是一个合法方案。所以，这两条边能保证，有合法方案的话，一定是A取1（选A+n节点）的情况。
3、A OR B=0.这要求A和B同时为0.方法和2类似，方向变一下而已，理由同上。
4、A XOR B=0.这要求A=B。所以，A为0时，B必须为0，同理B为0时，A必须为0.所以添加边：A->B,B->A,A+n->B+n,B+n->A+n。
有一大小为N的集合={x1,x2..xn}，xi = 0或1，现在给出它们之间的一些逻辑运算的结果(比如x1 and x2=1)；
逻辑运算有AND OR XOR三种；
问是否存在一种满足所有条件的取值方案。
代码如下：
#include <cstdio>
#include <cstring>
#define ll long long
#define MAXN 2017<<1
int grap[MAXN][MAXN] = {0};
int idx[MAXN] = {0};
int n, m;
//i 和 i+n。i表示这个元素取0，i+n表示这个元素取1
//连接某边是为了推出矛盾。x->y表示选x则必须选y
//注意方向
void build_grap(int a, int b, int c, char cc)//建图
{
if(cc == 'A')
{
if(c == 1)//a&b == 1 --->> (a==1 && b==1) && (a!=0 && b!=0)
{
grap[a][a+n] = grap[b][b+n] = 1;// a!= 0 && b != 0
grap[a+n][b+n] = grap[b+n][a+n] = 1;//a == 1 && b ==1
}
else //a&b == 0 --->> (a==1 && b==0) || (b==1 && a==0)
{
grap[a+n][b] = grap[b+n][a] = 1; //注意方向 是选了1才必须选0 不是选0才必须选1 在这里会出错
}
}
if(cc == 'O')//a | b
{
if(c == 1) // (a==1 && b==1) || (a==0 && b==1) || (a==1 && b==0)
{
// grap[a][b+n] = grap[b+n][a] = 1;//grap[b+n][a]错误，b为1时a可为0 也可为1
// grap[b][a+n] = grap[a+n][b] = 1;//同上
grap[a][b+n] = grap[b][a+n] = 1;
//grap[a+n][b+n] = grap[b+n][a+n] = 1;//不能添加
}
else // a==0 b==0 ; a!=1 ; b!=1
{
grap[a][b] = grap[b][a] = 1;
grap[a+n][a] = grap[b+n][a] = 1; //注意方向,先后关系
}
}
if(cc == 'X') //a^b
{
if(c == 1)//(a==1 && b==0) || (a==0 && b==1)
{
grap[a+n][b] = grap[b][a+n] = 1;//a==1 && b==0
grap[b+n][a] = grap[a][b+n] = 1;//a==0 && b==1
}
else // (a==1 && b==1) || (a==0 && b==0)
{
grap[a][b] = grap[b][a] = 1;
grap[a+n][b+n] = grap[b+n][a+n] = 1;//注意方向
}
}
}
int find_components(int n,int mat[][MAXN],int* iden) //模板
{
int ret=0,a[MAXN],b[MAXN],c[MAXN],d[MAXN],i,j,k,t;
for (k = 0; k < n; iden[k++]=0);
for (k = 0; k < n; k++)
if (!iden[k])
{
for (i = 0; i < n; i++)
a[i]=b[i]=c[i]=d[i]=0;
a[k]=b[k]=1;
for (t = 1; t;)
for (t = i = 0; i < n; i++)
{
if (a[i]&&!c[i])
for (c[i] = t = 1, j = 0; j < n; j++)
if (mat[i][j] && !a[j])
a[j] = 1;
if (b[i] && !d[i])
for (d[i] = t = 1, j = 0; j < n; j++)
if (mat[j][i] && !b[j])
b[j] = 1;
}
for (ret++, i = 0; i < n; i++)
if (a[i] & b[i])
iden[i]=ret;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int a, b, c;
char op[7];
for(int i = 0 ; i < m ; i++)
{
scanf("%d %d %d %s",&a,&b,&c,op);
build_grap(a,b,c,op[0]);
}
find_components(2*n,grap,idx); // 找环
int tmp = 0;
for(int i = 0 ; i < n ; ++i)
{
if(idx[i] == idx[i+n])
tmp = 1;//矛盾
}
if(tmp)
printf("NO\n");
else
printf("YES\n");
return 0;
}
POJ 3678 Katu Puzzle（2-sat 模板题）