某岛

… : "…アッカリ~ン . .. . " .. .
March 25, 2011

POJ 3678. Katu Puzzle

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