Brief description :

给定 n 个布尔变量，满足 m 组逻辑等式。
问是否存在一种赋值方案，使得所有的等式成立。

Analyse :

… 略。。。反正就是划到 2-SAT 就可以做了嘛。。
下面举两个例子。。

比如说 A or B == 1 这样的式子。。。
如果 A 赋值为 0 的话那么 B 必须是 1，因此连边 A0 -> B1。。。
。。。。。。

然后如果是 A and B == 1 的话。。。
此时如果 A 赋值为 0 ？。。不 。。A 不可以赋值为 0 。。。
不必拘泥于之前的限制。。。我们连一条 A0 -> A1 的边就可以了！

#include 
#include 
using namespace std;

const int INF = 0x7fffffff;
const int N = 2000;
vector adj[N];
int d[N], l[N], f[N];
int st[N], top, cnt;
int n, m;

void dfs(int u){
	d[u] = l[u] = ++cnt;
	st[top++] = u;
	for (int i=0;i



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

													Posted by 
													xiaodao													
													Category: 													POJ
 
													Tags: 2-SAT