P10969 Katu Puzzle

· · 题解

2-SAT 基础练习题。

解法

先考虑每一条限制如何转化“如果谁……那么谁必须……”。

先把每个点拆成两个点，分别对应值为 \text{true} 和值为 \text{false}。对于 X\land Y=0，显然，当 X=1 时 Y 必须为 0，当 Y=1 时 X 必须为 0，于是连边 (X,\neg Y),(Y,\neg X)。X\lor Y=1、X\oplus Y=0 和 X\oplus Y=1 也可以通过这样的转化得到建边方式。

那么问题来了：如果限制是 X\land Y=1 或者是 X\lor Y=1 怎么办？在这种情况下，X 和 Y 的值已经确定，我们该怎么处理？

想一想我们在输出可行方案的时候是怎么做的。每次我们比较两个点 X 与 \neg X 的拓扑序大小，选择拓扑序大的那个输出。那么当我们想要使得 X 被选中，就应该让 \neg X 向 X 连边，才能保证 X 的拓扑序比 \neg X 大，从而使 X 被选中。

然后剩下就是判断 X 和 \neg X 是不是在同一个强连通分量里面就行了。

::::info[Code]

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define Mem(a,b) memset ((a),(b),sizeof((a)))
#define eb emplace_back
#define pb push_back
using namespace std;
typedef long long ll;
constexpr int N = 2e5 + 15;

namespace FAST_IO {
#define IOSIZE (1<<20)
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
#define print(x,c) write(x),putchar(c),flush()
    template <typename T> inline void read (T &x) { x = 0; T f = 1;char ch = getchar ();while (!isdigit (ch)) {if (ch == '-') f = -1; ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar ();} x *= f;}
    template <> inline void read (double &x) { x = 0; int f = 1;char ch = getchar ();while (!isdigit (ch)) { if (ch == '-') f = -1; ch = getchar ();} while (isdigit (ch)) x = x * 10 + (ch - '0'), ch = getchar ();if (ch == '.') {ch = getchar (); for (double t = 0.1; isdigit (ch); t *= 0.1) x += t * (ch - '0'), ch = getchar ();}x *= f;}
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}
    template <typename T> inline void write (T x) { if (x < 0) putchar ('-'), x = -x; if (x > 9) write (x / 10); putchar (x % 10 + 48);}
    inline void write(char *x) { while (*x) putchar(*x++); }
    inline void write(const char *x) { while (*x) putchar(*x++); }
    inline void flush() { if (p3 != obuf) { fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}
}
using namespace FAST_IO;

int n, m;
int head[N], to[N << 1], nxt[N << 1], idx;
int dfn[N], low[N], tmp, stk[N], top, id[N], scc;
bool in_stk[N];

void add (int u, int v) {
    to[idx] = v;
    nxt[idx] = head[u];
    head[u] = idx ++;
}

void Tarjan (int u) {
    dfn[u] = low[u] = ++ tmp;
    stk[++ top] = u;
    in_stk[u] = true;
    loop (i, head[u], nxt[i]) {
        int v = to[i];
        if (!dfn[v]) {
            Tarjan (v);
            low[u] = min (low[u], low[v]);
        } else if (in_stk[v]) low[u] = min (low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int cur;
        ++ scc;
        do {
            cur = stk[top --];
            id[cur] = scc;
            in_stk[cur] = false;
        } while (u != cur);
    }
}

int main () {
    Mem (head, -1);
    read (n, m);
    for (int i = 1; i <= m; ++ i) {
        int u, v, w;
        char s[3];
        read (u, v, w, s);
        ++ u, ++ v;
        if (*s == 'A') {
            if (w == 1) add (u, u + n), add (v, v + n);
            else add (u + n, v), add (v + n, u);
        } else if (*s == 'O') {
            if (w == 1) add (u, v + n), add (v, u + n);
            else add (u + n, u), add (v + n, v);
        } else {
            if (w == 1) add (u, v + n), add (v, u + n), add (u + n, v), add (v + n, u);
            else add (u, v), add (v, u), add (u + n, v + n), add (v + n, u + n);
        }
    }
    for (int i = 1; i <= 2 * n; ++ i) {
        if (!dfn[i]) Tarjan (i);
    }
    for (int i = 1; i <= n; ++ i) {
        if (id[i] == id[i + n]) {
            print ("NO", '\n');
            return 0;
        }
    }
    print ("YES", '\n');
    return 0;
}

::::