Luogu P3007 奶牛议会

观前须知

本题解使用 CC BY-NC-SA 4.0 许可 。
同步发布于 Luogu 题解区。
更好的观看体验 请点这里 。

笔者的博客主页

正文

Luogu P3007 【USACO11JAN】 The Continental Cowngress G

前置知识： 2-SAT 、 Tarjan 。
（应该没有人会 2-sat 不会 tarjan 吧）

DAG DP 朴素做法

这道题除去输出 '?' 的部分是一道 2-SAT 的纯版子题。
其他题解基本使用了 DFS 来判断该情况。
这里提供一份 bitset 优化的 DAG DP 解法。
凭借着 bitset 强大的优化，成功跑到 34ms，轻松 rk1。

由于这道题的前半部分就是 2-SAT 的板子题，所以不再过多赘述。
感兴趣可见 Luogu P4782 【模板】2-SAT 。

那么考虑什么情况下可选也可不选，
发现当且仅当 \(x\) （表示法案 \(x\) 通过）和 \(x'\) （表示法案 \(x\) 不通过）不连通时可选可不选。
因为我们已经有了一个 DAG，可以求出它的 拓扑序 ，
那么不连通也就是拓扑序 靠后 的那一个节点的 祖先 中没有它的反节点。
强连通分量题做得多的 dalao 们应该已经想到这道题可以 DP 了。

小 trick：
Tarjan 求出的强连通分量编号是缩点后的图的 拓扑逆序 。
从 Tarjan 递归过程的角度思考一下很好证明。
……
不卖关子啦。
其实就是在搜索树上，由于递归类似于 栈 ，是 先进后出 的，
所以一个节点后代节点可在搜索树上后搜到，回溯时，后代节点先被统计强连通分量。
所以后代节点一定在祖先节点之前被统计，得到的顺序就是拓扑逆序了。

具体的 DP 方式是这样的：
缩点后，对于每个节点（这里是原图的强连通分量），维护一个 \(vis_u\) 数组，
\(vis_{u,v}=1\) 表示 \(v\) 在 \(u\) 的祖先节点中出现过，反之表示未出现过。
转移就是如果 \(v\) 在 \(u\) 的祖先节点出现过，则它肯定在 \(son(u)\) 的祖先节点中出现过。
特别地， \(vis_{u,u}=1\) 。
具体转移方式见代码：

// co[0] 存储强连通分量个数
// 这里使用了强连通分量是拓扑逆序的小 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];
}

那么如果一个法案可选也不可选，即不连通时有： \(vis_{u,v}=0\) ，其中 \(u\) 为拓扑序靠后的节点， \(v\) 为 \(u\) 的反节点
判断的具体代码如下：

for (int i = 1; i <= n; i++) {
    // i 表示通过，i+n 表示不通过
    // 判断拓扑序靠后的是哪个节点，vx=0 为 i，vx=1 为 i+n
    // co[u] 表示 u 节点所属的强连通分量
    vx = co[i] > co[i + n];
    // 利用三目运算简化语句
    // 若有祖先关系则输出 Y 或 N
    if (vis[co[vx ? i + n : i]][co[vx ? i : i + n]]) putchar(vx ? 'N' : 'Y');
    // 否则输出 ？
    else putchar('?');
}

好的那么现在我们已经有了一个 \(O(n^2)\) 的算法了。
但是还不够。

bitset

接下来我们来介绍今天的主角： bitset 。
我们知道，平常我们使用 bool 数组的时候，像是 bool vis[N]; 是要使用 \(8N\) bit 的空间的。
然而一个 bool 实际上也就是一个 0/1 的值，能不能只占 \(1\) bit 空间呢？
可以！我们写成 bitset vis 就可以了！
这里的 N 是 bitset 的位数，要求必须是整型常量。
bitset 同 bool 数组一样，支持形如 vis[u] 的访问和赋值。
然而它同时支持与、或、左/右移等操作。
可以理解为 bitset 是一个大的二进制数。

由于篇幅有限，bitset 的详细用法不会过多赘述，这里只介绍用来优化的部分。
更多内容可见这篇文章： C++ std::bitset 。

等一下，它支持或？
我们发现，我们程序中有这么一个操作：

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

这个操作相当于把 vis[e[i].v] 这个数组 整体或 上一个 vis[u] 。
那么我们就可以用 bitset 优化了！
开一个 bitset b[N]; 的数组， M 表示强连通分量个数上限，则我们的程序可以改写为：

bitset b[N];

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

/*...*/

// 因为 bitset 支持类似 bool数组 的操作，所以这段代码除了一个变量名外没有变化
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 做完了这道题目。
那么问题来了，优化后的空间复杂度肯定小了，时间复杂度呢？
直接给结论：
bitset 的单次整体与、或等操作复杂度为 \(\mathcal O(\frac{n}{w})\) 。
这里， \(n\) 指 bitset 的长度， \(w\) （不是 \(\omega\) ）为计算机字长，一般为 \(32\) 。
那么整体时间复杂度就是 \(\mathcal O(\frac{n^2}{w})\) 了，相当于在原先的复杂度上除了一个比较大的 \(\log\) 。
这样的时间复杂度就是非常优的了。

bitset 优化可以优化 floyd求传递闭包 等算法。
往往 \(10^4\) 的数据， \(\mathcal O(n^2)\) 无法通过，而 \(\mathcal O(\frac{n^2}{w})\) 就可以通过了。
所以说，bitset 的优化真的 非常强大 。

剩下的一些小细节放在代码的注释里了：
本代码 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;
    //这里是强连通分量个数，开这么大就能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;
        //三目运算简化
        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"));
        //建新图，这里直接用旧图开新节点的方式处理了
        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;
}

完结，撒花！~