UOJ168 元旦老人与丛林

网络流 + 神秘结论题目。

题意：给定 $n$ 个点，$m$ 条边的无向图，问能不能把边集划分成两部分，每一部分都是森林。$n\leq 2000, m\leq 4000$。

首先有一个结论：该无向图合法当且仅当任意子图都满足边数小于二倍点数 - 2 时可以找到方案。

证明不太会，大概感性理解一下吧。

现在我们要考虑的问题就是是否全部满足 $|E|\leq 2|V| - 2$。相当于要求 $|E| - 2|V|$ 的最大值。我们边拆点，每一个边向他的两个端点连边，然后相当于每一条边的权值是 1，每一个点的权值是 -2，然后有前提的选点。这样相当于是最大权闭合图，可以使用网络流在 $O(n ^ 2)$ 的时间内解决（因为权值是 $O(1)$ 级别的）。

注意到我们并不能选择空图，因为此时根据我们的判断一定不合法，所以我们需要强制选一个点（注意可以不选边）。那么此时，我们需要将 $u\to T$ 的边设为满流，如何操作呢？

首先暴力重建复杂度是 $O(n ^ 3)$，过不去，我们考虑在残留网络上接着跑。

考虑先将 $u\to T$ 的流量给退了，退流过程其实就是 $u\to S$ 做一遍流量上界为 $u\to S$ 容量 $c$ 的网络流，然后割掉 $u\to T$，暴力做一遍 $S$ 到 $T$ 的网络流，容易发现流量变化为 $O(1)$，所以单次 Dinic 时间复杂度 $O(n)$，总复杂度 $O(n ^ 2)$。但由于 Dinic 很玄学，没有限制容量也可以过（）。

下面考虑证明这个做法的正确性。先把 $u\to S$ 容量为 $c$ 的网络流退掉，这样考虑整张图的流量平衡，容易发现次数 $u$ 恰好少了 $c$ 的流量，这相当于我们割断了 $u\to T$ 并且使之满流，变化就是整个网络流的变化量，直接判断即可。

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<PII> edg(m + 1);
    MFGraph<int> mf(n + m + 2, m * 10);
    int S = n + m + 1, T = n + m + 2;
    for (int i = 1; i <= n; ++ i) mf.add(i, T, 2);
    for (int i = 1; i <= m; ++ i) mf.add(S, i + n, 1);
    for (int i = 1; i <= m; ++ i)
    {
        auto &[u, v] = edg[i];
        scanf("%d %d", &u, &v);
        mf.add(i + n, u, INF), mf.add(i + n, v, INF);
    }
    int curflow = 0;
    for (int u = 1; u <= n; ++ u)
    {
        // auto [u, v] = edg[i];
        mf.edg[(u - 1) << 1].w = 0;
        // mf.edg[(u - 1) << 1 | 1].w = mf.edg[(v - 1) << 1 | 1].w = 0;
        curflow -= mf.solve(u, S)/*, curflow -= mf.solve(v, S)*/;
        curflow += mf.solve(S, T);
        if (m - curflow + 2 > 2) return puts("No"), 0;
        mf.edg[(u - 1) << 1].w = 2;
    }
    puts("Yes");
    return 0;
}