POJ 2723 Get Luffy Out 二分答案+2-SAT判定

問題描述

有 N 對鑰匙（共 2N 把），每對中使用一把另一把消失。有 M 扇門，每扇門有兩把鎖，打開任意一把即可通過。門按順序排列。選擇 N 把鑰匙（每對選一把），求最多能打開前幾扇門。

解題思路

二分答案：設能打開前 mid 扇門，判定是否可行。
2-SAT 建模：

• 變量 x_i：第 i 把鑰匙是否被選中
• 每對鑰匙 (a, b)：a → ¬b，b → ¬a（互斥）
• 每扇門 (c, d)：¬c → d，¬d → c（至少選一把）

用 Tarjan 算法求強連通分量，若某變量與其否定在同一 SCC 則不可滿足。

關鍵代碼

struct TwoSAT {
    int n; vector> adj;
    vector dfn, low, scc_id, stk; vector in_stk;
    int dfs_time, scc_cnt;
    
    TwoSAT(int n) : n(n), adj(2*n) {}
    
    void add_implication(int u, int v) { adj[u].push_back(v); }
    void add_or(int u, int v) { // u ∨ v
        add_implication(u^1, v);
        add_implication(v^1, u);
    }
    void add_xor(int u, int v) { // u ⊕ v (互斥)
        add_implication(u, v^1);
        add_implication(v, u^1);
    }
    
    bool satisfiable() {
        // Tarjan SCC
        // 檢查 i 和 i^1 是否在同一 SCC
    }
};

bool check(int mid) {
    TwoSAT solver(2*N);
    for (int i = 0; i < N; ++i) {
        int a = key[i][0], b = key[i][1];
        solver.add_xor(a*2, b*2); // 每對選一把
    }
    for (int i = 0; i < mid; ++i) {
        int c = door[i][0], d = door[i][1];
        solver.add_or(c*2, d*2); // 門至少開一把鎖
    }
    return solver.satisfiable();
}

複雜度

二分 O(log M)，每次 2-SAT O(N + M)，總時間 O((N+M) log M)。