P14578 【模板】无源汇上下界可行流 题解

zrl123456 · 2025-12-26 21:16:44 · 题解

:::::info[题目基本信息] 考察：网络流，上下界网络流（省选/NOI-）。
题目简介：
给定一个 n 个点 m 条边的有向图，求出一个流使得：

• 对于第 i 条边，它的流量位于 [l_i,r_i] 之间。
• 对于点 u，它的流入流量等于流出流量。

若不存在报告无解。
数据范围：

• 1\le n\le 10^3
• 1\le m\le 10^4
• \forall i\in[1,m],0\le l_i\le r_i\le 10^5

  :::::

  算法介绍：

  观察一下，对于第 i 条边我们至少需要流 l_i 的流量，那么我们只流这些可能会使某个点的流入流量不等于流出流量，不妨以流入流量比流出流量多 k 为例。
  这时，我们会要求额外的流量中流入流量比流出流量少 k，但是我们网络流只能跑流入流量等于流出流量的，怎么办呢？
  这个是好办的，我们建一个超级源点，令超级源点向其连一条流量为 k 的即可，顺带着也解决了没有源汇的问题。
  对于流入流量比流出流量少的建超级汇点即可。
  最后判断一下超级汇点是否满流。

  正确性证明：

  上述算法的正确性基本没有问题，唯一的问题是能否保证加入的超级源点与点的边能否流满，不然没办法保证流入流量和流出流量的差值一定了。
  其实这个是比较简单的，你注意到超级源点向所有点连成的边的流量等于超级汇点从所有点连来的边的流量（这是因为每条边都会贡献一次流入流量和流出流量），那么要想超级汇点满流这些边必须流满。

  代码实现：

  这一部分是非常简单的，根据上述建出边后直接套用 dinic 模板即可。

时间复杂度为 \Theta(n^2m)（网络流题目时间复杂度无较大参考价值），空间复杂度为 \Theta(n+m)。

code