题解

POJ 3678 Katu Puzzle


2-SAT板子题,把我上一篇博客里的表格照搬就可以了。

Source Code

#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int MAXN = 2e4 + 7;
const int MAXM = 1e6 + 7;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int n, m;
int head[MAXN], cnt;
int dfn[MAXN], low[MAXN], mark[MAXN], cntScc, ts;
bool inStack[MAXN];
std::stack<int> stack;
void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
void addClause(int a, int va, int b, int vb) {
    add(a + n * va, b + n * (!vb));
    add(b + n * vb, a + n * (!va));
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stack.push(u);
    inStack[u] = true;
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!dfn[v]) Tarjan(v), low[u] = std::min(low[u], low[v]);
        else if (inStack[v]) low[u] = std::min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++cntScc;
        do {
            mark[u] = cntScc, inStack[u] = false;
            u = stack.top(), stack.pop();
        } while (low[u] != dfn[u]);
    }
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &m);
    int u, v, val;
    char type[5];
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d %s", &u, &v, &val, type + 1);
        u++, v++;
        if (type[1] == 'X') {
            if (val) addClause(u, 1, v, 1), addClause(u, 0, v, 0);
            else addClause(u, 0, v, 1), addClause(u, 1, v, 0);
        } else if (type[1] == 'A') {
            if (val) addClause(u, 1, v, 1), addClause(u, 0, v, 1), addClause(u, 1, v, 0);
            else addClause(u, 0, v, 0);
        } else {
            if (val) addClause(u, 1, v, 1);
            else addClause(u, 0, v, 0), addClause(u, 0, v, 1), addClause(u, 1, v, 0);
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) Tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        if (mark[i] == mark[i + n]) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注