P4298 Solution

· · 题解

前置知识: 称有向图 G = (V, E) 的子图 H \subset G 是闭合子图, 如果 \forall (u, v) \in E, (u \in H \Rightarrow v \in H). 现每一点 u 有一整数点权 w_u, 且子图的权值为子图中所有点权之和, 求该无环图的最大权闭合子图, 可以用网络流解决.

第一问可以转化为最大权闭合子图问题. 在新图中将点 u 拆为 u_1, u_2, 点权分别为 -1 和 1, 同时连边 (u_1, u_2). 对原图中的一条有向边 (u, v), 在新图中连边 (u_2, v_1). 对新图求最大权闭合子图, 即为第一问的答案.

设新图是 G, H \subset G 是 G 的一个最大权闭合子图. 那么这张图对应的方案中, 点 u 可以作为祭祀点当且仅当 u_1 \notin H \land u_2 \in H.

对第二问, 相当于构造出一个最大权闭合子图. 在最大权闭合子图问题中, 一个最大权闭合子图 H \subset G 可以唯一对应所构图的一个最小割 (S, T), 其中 u \in H \Leftrightarrow u \in T \land (\forall (v, u) \in E, v \in S). 据此可以先构造出最小割, 再构造方案.

第三问相当于对每个 u, 判断是否存在最小割 (S, T), 使得 u_1 \in S \land u_2 \in T. 注意到割 (S, T) 是最小割当且仅当在残量网络中, S 是闭合子图, 即 \forall (u, v) \in \text{残量网络}, (u \in S \Rightarrow v \in S). 令 f(u, v) 表示残量网络中是否存在 u 到 v 的路径. 那么存在最小割 (S, T), 使得 u_1 \in S \land u_2 \in T 的等价条件是 \lnot f(s, u_2) \land \lnot f(u_1, u_2) \land \lnot f(u_1, t), 其中 s 和 t 是网络中的源汇点.

本做法只需跑一遍网络流, 由于边权均为 1 或 +\infty, 复杂度为 \mathcal O(m \sqrt n + n \times (n+m)) = \mathcal O(nm).

下面是使用了 AtCoder Library 的参考代码.

#include <cstdio>
#include <vector>
#include <atcoder/maxflow>
const int INF = 0x3F3F3F3F;

signed main() {
    int n, m;
    scanf("%d%d", &n, &m);
    atcoder::mf_graph<int> mf(n * 2 + 2);
    int S = 2 * n, T = S + 1;

    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        mf.add_edge(u + n, v, INF);
    }

    for (int i = 0; i < n; ++i) {
        mf.add_edge(S, i + n, 1);
        mf.add_edge(i, T, 1);
        mf.add_edge(i, i + n, INF);
    }

    printf("%d\n", n - mf.flow(S, T));
    auto min_cut = mf.min_cut(S);
    for (int i = 0; i < n; ++i)
        putchar(!min_cut[i] && min_cut[i + n] ? '1' : '0');
    puts("");

    std::vector<std::vector<int> > e(2 * n + 2);
    for (auto o : mf.edges()) {
        if (o.cap != o.flow)
            e[o.from].push_back(o.to);
        if (o.flow)
            e[o.to].push_back(o.from);
    }
    std::vector<std::vector<int> > reach(2 * n + 2, std::vector<int>(2 * n + 2));

    for (int i = 0; i < 2 * n + 2; ++i) {
        std::queue<int> q;
        q.push(i);
        reach[i][i] = true;
        for (; !q.empty(); q.pop())
            for (auto to : e[q.front()])
                if (!reach[i][to]) {
                    reach[i][to] = true;
                    q.push(to);
                }
    }

    for (int i = 0; i < n; ++i)
        putchar(!reach[i + n][T] && !reach[i + n][i] && !reach[S][i] ? '1' : '0');
    puts("");
    return 0;
}