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.