UVA 1391 Astronauts：2-SAT 模型解任務分配

UVA 1391 Astronauts：2-SAT 解法

題目大意

n 位太空人，年齡小於平均值可執行任務 A、C；大於等於平均值可執行 B、C。部分太空人互相仇恨，不能分配同一任務。求滿足條件的分配方案。

2-SAT 建模

• 每人一個布林變數：true 表示選第一類任務（A 或 B），false 表示選 C。
• 同類太空人（皆 < 平均或皆 ≥ 平均）：不能同任務 → (x ∨ y) ∧ (¬x ∨ ¬y)（異或關係）。
• 不同類太空人：不能同任務 → (x ∨ y)（至少一個選第一類）。

Kosaraju / Tarjan 求強連通分量

struct TwoSAT {
    int n; vector g[2*MAXN]; bool mark[2*MAXN]; int S[2*MAXN], sn;
    void add_or(int u, int uval, int v, int vval) { // uval/vval: 0=false, 1=true
        g[u*2+uval^1].push_back(v*2+vval);
        g[v*2+vval^1].push_back(u*2+uval);
    }
    bool dfs(int u) {
        if (mark[u^1]) return false;
        if (mark[u]) return true;
        mark[u]=true; S[sn++]=u;
        for (int v:g[u]) if (!dfs(v)) return false;
        return true;
    }
    bool solve() {
        for (int i=0;i<2*n;i+=2)
            if (!mark[i] && !mark[i+1]) {
                sn=0;
                if (!dfs(i)) { for (int j=0;j