上下界网络流

无源汇上下界可行流

给定一个流网络，无源汇（即所有点都需要满足流量守恒），每条边有下界 \(a(u, v)\) 和上界 \(b(u, v)\)，求可行流。

考虑先将所有边流设为下界，然后再进行调整。对于原图中的边 \((u, v)\)，连边 \((u, v, b(u, v) - a(u, v))\)。定义 \(g(u) = \displaystyle\sum_{(v, u) \in \mathbf E} a(v, u) - \sum_{(u, v) \in \mathbf E} a(u, v)\)，即每个点流入与流出的流量之差。我们新建超级源点 \(S\) 和超级汇点 \(T\)。若 \(g(u) > 0\)，说明流入 \(u\) 的流量比流出的流量多 \(g(u)\)，连边 \((S, u, g(u))\)；若 \(g(u) < 0\)，说明流入 \(u\) 的流量比流出的流量少 \(-g(u)\)，连边 \((u, T, -g(u))\)。对新图求最大流，因为增广需要遵循流量守恒，如果从 \(S\) 出发和到达 \(T\) 的流量都流满，那么对应与其相连的点在原图中也满足流量守恒了。实际上，检验其中任意一个即可。

每条边的下界加上在新图中的流量即为一个可行流。

有源汇上下界可行流

给定一个流网络，有源汇，每条边有下界 \(a(u, v)\) 和上界 \(b(u, v)\)，求可行流。

Warning

下面说的 \(s\) 和 \(t\) 与无源汇上下界可行流中的 \(S\) 和 \(T\) 不同。

对于一个普通的流网络，从 \(s\) 流出的净流量与流入 \(t\) 的净流量相等，所以我们可以在原图中加一条从 \(t\) 到 \(s\)，下界为 \(0\)，上界为 \(\infty\) 的流，这样就转化为无源汇上下界可行流了，流的值即为新图中 \(t\) 到 \(s\) 的流量。

有源汇上下界最小流

给定一个流网络，有源汇，每条边有下界 \(a(u, v)\) 和上界 \(b(u, v)\)，求最小流。

先求出可行流，再只保留原图中的边，求 \(t\) 到 \(s\) 的最大流（即尽可能多的退回流量），用可行流的值减去求出的最大值即为答案。在实现时只需要删掉 \(t\) 到 \(s\) 的边（因为只有这一条边会对接下来求的最大流有影响），然后跑最大流即可。

有源汇上下界最大流

给定一个流网络，有源汇，每条边有下界 \(a(u, v)\) 和上界 \(b(u, v)\)，求最小流。

先求出可行流，再只保留原图中的边，求 \(s\) 到 \(t\) 的最大流（即尽可能多的添加流量），用可行流的值加上求出的最大值即为答案。实际上，因为当前 \(t\) 到 \(s\) 的流量为可行流的值，将这条边的流量全部退回对于这次最大流的影响即为可行流的值。因此直接在新图跑 \(s\) 到 \(t\) 的最大流即为有源汇上下界最大流。

上下界费用流

直接将上面对应问题的最大流改为最小/大费用流即可。