某島

… : "…アッカリ~ン . .. . " .. .
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