题解 CF708D 【Incorrect Flow】

这是一个有源汇带上下界最小费用可行流的问题，然而这个“带上下界”其实是假的。 注意到，只要 $f$ 在 $0 \sim c$ 内，就可以用 $1$ 的代价更改，但是一旦要超过 $c$，就需要同时更改 $c$，相当于代价为 $2$。 对 $f \le c$ 的边和 $f > c$ 的边分开考虑： - 如果 $f \le c$，则最终的 $f'$ 可以减小或增大，故连如下三条边： 1. 减小 $f$：也就是从 $v$ 到 $u$ 退流，连 $v \to u$，容量为 $f$，费用为 $1$。 2. 增大 $f$（$f \le c$ 的部分）：连 $u \to v$，容量为 $(c - f)$，费用为 $1$。 3. 增大 $f$（$f > c$ 的部分）：连 $u \to v$，容量为 $\infty$，费用为 $2$。 - 如果 $f > c$，则至少要花费 $(f - c)$ 的代价，且在 $c \le f' \le f$ 时取到，故先贡献 $(f - c)$，连如下三条边： 1. 减小 $f$，最终的 $f'$ 在 $c \sim f$ 之间：连 $v \to u$，容量为 $(f - c)$，费用为 $0$。 2. 减小 $f$，最终的 $f' \le c$：连 $v \to u$，容量为 $c$，费用为 $1$。 3. 增大 $f$：连 $u \to v$，容量为 $\infty$，费用为 $2$。 然后对于初始的每条边，连 $u \to v$，容量下界和上界均为 $f$，费用为 $0$。 实际上，因为本题中的上下界把“有源汇带上下界可行流”转化成普通最大流，就是： 新建超级源和超级汇 $S, T$。 如果 $u$ 点**流入比流出多**，就连 $S \to u$，容量为流入流出的差值，费用为 $0$。 如果 $u$ 点**流出比流入多**，就连 $u \to T$，容量为流出流入的差值，费用为 $0$。 最后，为了取消原来的源汇，新建一条 $n \to 1$，容量为 $\infty$，费用为 $0$。 然后跑一次超级源到超级汇的最小费用最大流，一定是满流的，转化回原图就是一个最小费用可行流了。 如果使用 SPFA 辅助实现的类 Dinic 算法求最小费用最大流，时间复杂度为 $\mathrm{MCMF}( \!\left< |V|, |E|, F \right>\! = \!\left< \mathcal O(n), \mathcal O(n + m), \mathcal O (mv) \right>) = \mathcal O (n (n + m) m v)$，其中 $v$ 为值域，本题中为 ${10}^6$。 时间复杂度为 $\mathcal O (n (n + m) m v)$，[评测链接](https://codeforces.com/contest/708/submission/72747094)。