twosat.cpp
Bài toán
Cho m biến logic: a1, a2, ... , am và một biểu thức logic C có dạng:
C = (u1|v1) & ... & (un|vn)
Trong đó ui và vi (1 ≤ i ≤ n) được thay bằng biển logic aj hoặc (!aj) nào đó. (1 ≤ j ≤ m)
Hãy gán giá trị TRUE/FALSE cho các biến a1, a2, ..., am sao cho biểu thức C nhận giá trị TRUE, hoặc
thông báo không thể làm được.
Độ phức tạp
O(m+n)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <stack>
using namespace std;
#define negativearray(temp, type, name, size) type temp[size]; type *name = temp + (size / 2)
void minimize(int &a, int b) {
if (a > b)
a = b;
}
int m, n;
negativearray(asdfjh, vector<int>, a, 102309);
negativearray(weryjj, vector<int>, ar, 102309);
negativearray(asfjhh, int, value, 102309);
negativearray(asdklf, int, num, 102309);
negativearray(asiodf, int, low, 102309);
negativearray(weruiy, int, label, 102309);
void setFalse(int u) {
int i, v;
if (value[u] == 2)
return;
value[u] = 2;
for (int i = 0; i < ar[u].size(); i++)
setFalse(ar[u][i]);
}
int cnt = 0;
stack<int> st;
void NIE() {
puts("NO");
exit(0);
}
void visit(int u) {
//printf("visit(%d)\n", u);
num[u] = ++cnt;
low[u] = num[u];
st.push(u);
for (int i = 0; i < a[u].size(); ++i) {
int v = a[u][i];
if (num[v])
minimize(low[u], num[v]);
else {
visit(v);
minimize(low[u], low[v]);
}
}
int v;
if (num[u] == low[u])
do {
v = st.top();
st.pop();
num[v] = low[v] = 1000111000;
label[v] = u;
//printf("%d in %d\n", v, u);
if (value[u] == 2)
continue;
if (value[v] == 2)
NIE();
else
value[v] = 1;
setFalse(-v);
} while (u != v);
}
vector<int> T;
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
int p, q;
scanf("%d%d", &p, &q);
a[-p].push_back(q);
a[-q].push_back(p);
ar[q].push_back(-p);
ar[p].push_back(-q);
}
for (int i = 1; i <= n; i++)
if (num[i] == 0)
visit(i);
// for (i=1; i<=n; i++) printf(i==n?"%d\n":"%d ", value[i]);
for (int i = 1; i <= n; i++)
if (label[i] == label[-i])
NIE();
for (int i = 1; i <= n; i++)
if (value[i] == value[-i])
NIE();
for (int i = 1; i <= n; i++)
if (value[i] == 1)
T.push_back(i);
printf("YES\n%d\n", T.size());
for (int i = 0; i < T.size(); i++)
printf("%d ", T[i]);
printf("\n");
}
Nhận xét
Code này đã được dùng để nộp cho một bài tập trên SPOJ.