Luogu P3007 奶牛議會(huì)

觀前須知

本題解使用 CC BY-NC-SA 4.0 許可 。
同步發(fā)布于 Luogu 題解區(qū)。
更好的觀看體驗(yàn) 請(qǐng)點(diǎn)這里 。

筆者的博客主頁

正文

Luogu P3007 【USACO11JAN】 The Continental Cowngress G

前置知識(shí)： 2-SAT 、 Tarjan 。
（應(yīng)該沒有人會(huì) 2-sat 不會(huì) tarjan 吧）

DAG DP 樸素做法

這道題除去輸出 '?' 的部分是一道 2-SAT 的純版子題。
其他題解基本使用了 DFS 來判斷該情況。
這里提供一份 bitset 優(yōu)化的 DAG DP 解法。
憑借著 bitset 強(qiáng)大的優(yōu)化，成功跑到 34ms，輕松 rk1。

由于這道題的前半部分就是 2-SAT 的板子題，所以不再過多贅述。
感興趣可見 Luogu P4782 【模板】2-SAT 。

那么考慮什么情況下可選也可不選，
發(fā)現(xiàn)當(dāng)且僅當(dāng) \(x\) （表示法案 \(x\) 通過）和 \(x'\) （表示法案 \(x\) 不通過）不連通時(shí)可選可不選。
因?yàn)槲覀円呀?jīng)有了一個(gè) DAG，可以求出它的 拓?fù)湫? ，
那么不連通也就是拓?fù)湫? 靠后 的那一個(gè)節(jié)點(diǎn)的 祖先 中沒有它的反節(jié)點(diǎn)。
強(qiáng)連通分量題做得多的 dalao 們應(yīng)該已經(jīng)想到這道題可以 DP 了。

小 trick：
Tarjan 求出的強(qiáng)連通分量編號(hào)是縮點(diǎn)后的圖的 拓?fù)淠嫘? 。
從 Tarjan 遞歸過程的角度思考一下很好證明。
……
不賣關(guān)子啦。
其實(shí)就是在搜索樹上，由于遞歸類似于 棧 ，是 先進(jìn)后出 的，
所以一個(gè)節(jié)點(diǎn)后代節(jié)點(diǎn)可在搜索樹上后搜到，回溯時(shí)，后代節(jié)點(diǎn)先被統(tǒng)計(jì)強(qiáng)連通分量。
所以后代節(jié)點(diǎn)一定在祖先節(jié)點(diǎn)之前被統(tǒng)計(jì)，得到的順序就是拓?fù)淠嫘蛄恕?

具體的 DP 方式是這樣的：
縮點(diǎn)后，對(duì)于每個(gè)節(jié)點(diǎn)（這里是原圖的強(qiáng)連通分量），維護(hù)一個(gè) \(vis_u\) 數(shù)組，
\(vis_{u,v}=1\) 表示 \(v\) 在 \(u\) 的祖先節(jié)點(diǎn)中出現(xiàn)過，反之表示未出現(xiàn)過。
轉(zhuǎn)移就是如果 \(v\) 在 \(u\) 的祖先節(jié)點(diǎn)出現(xiàn)過，則它肯定在 \(son(u)\) 的祖先節(jié)點(diǎn)中出現(xiàn)過。
特別地， \(vis_{u,u}=1\) 。
具體轉(zhuǎn)移方式見代碼：

// co[0] 存儲(chǔ)強(qiáng)連通分量個(gè)數(shù)
// 這里使用了強(qiáng)連通分量是拓?fù)淠嫘虻男?trick
for (int u = co[0]; u; u--) {
    vis[u][u] = true;
    for (int i = head[u]; i; i = e[i].nxt) 
        for(int j = 1; j <= co[0]; j++)
            vis[e[i].v][j] |= vis[u][j];
}

那么如果一個(gè)法案可選也不可選，即不連通時(shí)有： \(vis_{u,v}=0\) ，其中 \(u\) 為拓?fù)湫蚩亢蟮墓?jié)點(diǎn)， \(v\) 為 \(u\) 的反節(jié)點(diǎn)
判斷的具體代碼如下：

for (int i = 1; i <= n; i++) {
    // i 表示通過，i+n 表示不通過
    // 判斷拓?fù)湫蚩亢蟮氖悄膫�(gè)節(jié)點(diǎn)，vx=0 為 i，vx=1 為 i+n
    // co[u] 表示 u 節(jié)點(diǎn)所屬的強(qiáng)連通分量
    vx = co[i] > co[i + n];
    // 利用三目運(yùn)算簡(jiǎn)化語句
    // 若有祖先關(guān)系則輸出 Y 或 N
    if (vis[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
    // 否則輸出 ？
    else putchar('?');
}

好的那么現(xiàn)在我們已經(jīng)有了一個(gè) \(O(n^2)\) 的算法了。
但是還不夠。

bitset

接下來我們來介紹今天的主角： bitset 。
我們知道，平常我們使用 bool 數(shù)組的時(shí)候，像是 bool vis[N]; 是要使用 \(8N\) bit 的空間的。
然而一個(gè) bool 實(shí)際上也就是一個(gè) 0/1 的值，能不能只占 \(1\) bit 空間呢？
可以！我們寫成 bitset vis 就可以了！
這里的 N 是 bitset 的位數(shù)，要求必須是整型常量。
bitset 同 bool 數(shù)組一樣，支持形如 vis[u] 的訪問和賦值。
然而它同時(shí)支持與、或、左/右移等操作。
可以理解為 bitset 是一個(gè)大的二進(jìn)制數(shù)。

由于篇幅有限，bitset 的詳細(xì)用法不會(huì)過多贅述，這里只介紹用來優(yōu)化的部分。
更多內(nèi)容可見這篇文章： C++ std::bitset 。

等一下，它支持或？
我們發(fā)現(xiàn)，我們程序中有這么一個(gè)操作：

for(int j = 1; j <= co[0]; j++)
    vis[e[i].v][j] |= vis[u][j];

這個(gè)操作相當(dāng)于把 vis[e[i].v] 這個(gè)數(shù)組 整體或 上一個(gè) vis[u] 。
那么我們就可以用 bitset 優(yōu)化了！
開一個(gè) bitset b[N]; 的數(shù)組， M 表示強(qiáng)連通分量個(gè)數(shù)上限，則我們的程序可以改寫為：

bitset b[N];

for (int u = co[0]; u; u--) {
    b[u][u] = true;
    // 利用 bitset 的或操作快速轉(zhuǎn)移
    for (int i = head[u]; i; i = e[i].nxt) b[e[i].v] |= b[u];
}

/*...*/

// 因?yàn)?bitset 支持類似 bool數(shù)組 的操作，所以這段代碼除了一個(gè)變量名外沒有變化
for (int i = 1; i <= n; i++) {
    vx = co[i] > co[i + n];
    if (b[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
    else putchar('?');
}

那么我們就用 bitset 做完了這道題目。
那么問題來了，優(yōu)化后的空間復(fù)雜度肯定小了，時(shí)間復(fù)雜度呢？
直接給結(jié)論：
bitset 的單次整體與、或等操作復(fù)雜度為 \(\mathcal O(\frac{n}{w})\) 。
這里， \(n\) 指 bitset 的長(zhǎng)度， \(w\) （不是 \(\omega\) ）為計(jì)算機(jī)字長(zhǎng)，一般為 \(32\) 。
那么整體時(shí)間復(fù)雜度就是 \(\mathcal O(\frac{n^2}{w})\) 了，相當(dāng)于在原先的復(fù)雜度上除了一個(gè)比較大的 \(\log\) 。
這樣的時(shí)間復(fù)雜度就是非常優(yōu)的了。

bitset 優(yōu)化可以優(yōu)化 floyd求傳遞閉包 等算法。
往往 \(10^4\) 的數(shù)據(jù)， \(\mathcal O(n^2)\) 無法通過，而 \(\mathcal O(\frac{n^2}{w})\) 就可以通過了。
所以說，bitset 的優(yōu)化真的 非常強(qiáng)大 。

剩下的一些小細(xì)節(jié)放在代碼的注釋里了：
本代碼 34ms 的提交記錄 。

#include

using namespace std;

class FD {
private:
    inline static int Read() {
        int r = 0, f = 0, c = getchar();
        while ((c < '0' || c > '9') && ~c) { f |= c == '-', c = getchar(); }
        while (c >= '0' && c <= '9') { r = (r << 1) + (r << 3) + (c ^ 48), c = getchar(); }
        return f ? -r : r;
    }

    static constexpr int AwA = 2e3 + 10;
    static constexpr int QwQ = 8e3 + 10;
    //這里是強(qiáng)連通分量個(gè)數(shù)，開這么大就能ac
    static constexpr int PwP = 360;

    struct Edge {
        int nxt, v;
    } e[QwQ << 1];
    int head[AwA << 1], ecnt;

    inline void AddEdge(int u, int v) { e[++ecnt] = {head[u], v}, head[u] = ecnt; }

    int n, m;
    int dfn[AwA], low[AwA], co[AwA], stk[AwA];
    bitset b[AwA];

    void Tarjan(int u) {
        stk[++stk[0]] = u;
        dfn[u] = low[u] = ++dfn[0];
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
            else if (!co[v]) low[u] = min(low[u], dfn[v]);
        }
        if (dfn[u] == low[u]) {
            co[u] = ++co[0];
            while (stk[stk[0]] != u) co[stk[stk[0]--]] = co[0];
            stk[0]--;
        }
    }

public:
    inline void Main() {
        n = Read(), m = Read();
        int x, y;
        bool vx, vy;
        //三目運(yùn)算簡(jiǎn)化
        while (m--) {
            x = Read(), vx = getchar() == 'N';
            y = Read(), vy = getchar() == 'N';
            AddEdge(vx ? x : x + n, vy ? y + n : y);
            AddEdge(vy ? y : y + n, vx ? x + n : x);
        }
        for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) Tarjan(i);
        //判無解
        for (int i = 1; i <= n; i++) if (co[i] == co[i + n]) return void(puts("IMPOSSIBLE"));
        //建新圖，這里直接用舊圖開新節(jié)點(diǎn)的方式處理了
        for (int u = 1; u <= 2 * n; u++)
            for (int i = head[u]; i; i = e[i].nxt)
                if (co[e[i].v] != co[u]) AddEdge(co[u] + n * 2, co[e[i].v]);

        //DAG DP
        for (int u = co[0]; u; u--) {
            b[u][u] = true;
            for (int i = head[u + 2 * n]; i; i = e[i].nxt) b[e[i].v] |= b[u];
        }
        //輸出答案
        for (int i = 1; i <= n; i++) {
            vx = co[i] > co[i + n];
            if (b[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
            else putchar('?');
        }
        putchar('\n');
    }
} Fd;

int main() {
    Fd.Main();
    return 0;
}

完結(jié)，撒花！~