题解

思路分析

这是一道经典的 2-SAT 问题，需要判断布尔可满足性并构造解。

问题建模

• 有 $m$ 个开关，每个开关有两种状态：闭合（1）或断开（0）
• 有 $n$ 个管道，每个管道有两个阀门，分别由开关控制
• 阀门状态由开关状态和控制模式决定
• 目标：找到一组开关状态使所有管道关闭

核心思路

1. 转化为2-SAT

对于每个管道 $(a, s_a, b, s_b)$，要关闭它，至少有一个阀门要关闭。

转化为逻辑式（CNF）：

• 如果 $s_a = 0$：开关 $a$ 断开时阀门关闭，即 $\neg x_a$
• 如果 $s_a = 1$：开关 $a$ 闭合时阀门关闭，即 $x_a$

管道关闭的条件：$(\text{valve}_a \text{ closed}) \lor (\text{valve}_b \text{ closed})$

转化为蕴含关系：

• valve_a 开 $\Rightarrow$ valve_b 关
• valve_b 开 $\Rightarrow$ valve_a 关

2. 建图

用变量 $2i$ 表示开关 $i$ 闭合，$2i+1$ 表示开关 $i$ 断开。

对于每个管道，添加两条有向边：

(valve_a 开的状态) -> (valve_b 关的状态)
(valve_b 开的状态) -> (valve_a 关的状态)

3. Tarjan求强连通分量

使用 Tarjan 算法求 SCC：

• 如果 $x_i$ 和 $\neg x_i$ 在同一个 SCC 中，无解
• 否则有解，根据拓扑序选择赋值

4. 构造解

对于每个开关 $i$：

• 如果 $col[2i] > col[2i+1]$（拓扑序更大），选择 $2i+1$（断开）
• 否则选择 $2i$（闭合）

算法步骤

1. 读入数据，建立2-SAT图
2. 运行Tarjan算法求SCC
3. 判断可行性（$x_i$ 和 $\neg x_i$ 不在同一SCC）
4. 根据拓扑序构造解

复杂度分析

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n + m)$

#include <bits/stdc++.h>
#define RNG(V_, A_, B_) for (int V_ = (A_), V_##_END = (B_); V_ <= V_##_END; V_++)
#define IRNG(V_, A_, B_) for (int V_ = (A_), V_##_END = (B_); V_ >= V_##_END; V_--)
using namespace std;
const int MAXN = 1e6+10;
int n, m;
struct TwoSAT {
    vector<int> G[MAXN];
    void add(int i, int j) { G[i^1].push_back(j), G[j^1].push_back(i); }
    int dfn[MAXN], low[MAXN], dfncnt, instk[MAXN], stk[MAXN], stktop, col[MAXN], colcnt;
    void tarjan(int u) {
        dfn[u] = low[u] = ++dfncnt, instk[u] = true, stk[++stktop] = u;
        for (auto v : G[u]) {
            if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
            else if (instk[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            int v, c = ++colcnt;
            do {
                instk[v = stk[stktop--]] = false;
                col[v] = c;
            } while (v != u);
        }
    }
    bool solve() {
        RNG(u, 2, 2*n+1) {
            if (!dfn[u]) tarjan(u);
        }
        RNG(u, 1, n) {
            if (col[2*u] == col[2*u+1]) return false;
        }
        return true;
    }
} twosat;
int main() {
    scanf("%d%d", &m, &n);
    RNG(_, 1, m) {
        int i, a, j, b;  scanf("%d%d%d%d", &i, &a, &j, &b);
        twosat.add(i*2+a, j*2+b);
    }
    if (twosat.solve()) {
        RNG(i, 1, n) printf("%d\n", twosat.col[i*2] > twosat.col[i*2+1]);
    } else printf("IMPOSSIBLE\n");
}

题解

题目要判断是否能够通过设置每个开关的状态，使所有管道至少有一个阀门关闭。把“开关 $i$ 取值为 0/1”视作布尔变量 $x_i$，单个阀门处于关闭状态意味着 “$x_i = s$”（其中 $s$ 由输入给出）。一个管道有两个阀门，只要其中至少一个关闭即可，于是得到一个析取子句 $(x_a = s_a) \lor (x_b = s_b)$。这样所有约束都变成了 2-SAT。

实现时将变量 $x_i$ 的正反两个取值映射为下标 $2i$ 与 $2i+1$，add(u, v) 按 2-SAT 标准建边（$\lnot u \rightarrow v$、$\lnot v \rightarrow u$）。对整个含义图执行 Tarjan 强连通分量分解：如果某个变量的两个取值落入同一个 SCC，则无解；否则按照 SCC 拓扑序比较 col[2*i] 与 col[2*i+1] 的先后，较大的那一个代表赋值为真。

这种建模可以在线性时间内（对于每条输入管道生成常数条边）完成，并用 Tarjan 在 $O(n+m)$ 复杂度内求解。最后输出每个开关应该取的状态即可；若检测到矛盾则输出 IMPOSSIBLE。

#include <bits/stdc++.h>
#define RNG(V_, A_, B_) for (int V_ = (A_), V_##_END = (B_); V_ <= V_##_END; V_++)
#define IRNG(V_, A_, B_) for (int V_ = (A_), V_##_END = (B_); V_ >= V_##_END; V_--)
using namespace std;
const int MAXN = 1e6+10;
int n, m;
struct TwoSAT {
    vector<int> G[MAXN];
    void add(int i, int j) { G[i^1].push_back(j), G[j^1].push_back(i); }
    int dfn[MAXN], low[MAXN], dfncnt, instk[MAXN], stk[MAXN], stktop, col[MAXN], colcnt;
    void tarjan(int u) {
        dfn[u] = low[u] = ++dfncnt, instk[u] = true, stk[++stktop] = u;
        for (auto v : G[u]) {
            if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
            else if (instk[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            int v, c = ++colcnt;
            do {
                instk[v = stk[stktop--]] = false;
                col[v] = c;
            } while (v != u);
        }
    }
    bool solve() {
        RNG(u, 2, 2*n+1) {
            if (!dfn[u]) tarjan(u);
        }
        RNG(u, 1, n) {
            if (col[2*u] == col[2*u+1]) return false;
        }
        return true;
    }
} twosat;
int main() {
    scanf("%d%d", &m, &n);
    RNG(_, 1, m) {
        int i, a, j, b;  scanf("%d%d%d%d", &i, &a, &j, &b);
        twosat.add(i*2+a, j*2+b);
    }
    if (twosat.solve()) {
        RNG(i, 1, n) printf("%d\n", twosat.col[i*2] > twosat.col[i*2+1]);
    } else printf("IMPOSSIBLE\n");
}