题解 CF708D 【Incorrect Flow】

小粉兔 · 2020-03-09 02:27:25 · 题解

这是一个有源汇带上下界最小费用可行流的问题，然而这个“带上下界”其实是假的。

注意到，只要 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)，评测链接。