网络流

最大流

常用的算法： Edmond-Karps 和 Dinic

无源汇有上下界可行流

首先明确问题：现在这个问题叫做 “可行流” 而不是 “最大流”，是因为现在有了额外的每条边流量上下界的要求，所以未必存在一个流满足所有这些条件。

假设一条边的流量下界是 $low$ 、上界是 $high$ ，则基本的想法是先固定让这条边流过 $low$ ，然后剩下的 $high-low$ 放在算法里跑。但是如果直接把这个边的流量预先设为 $low$ ，建好的图不一定满足对于每个点都有流出等于流入。

解决方法是建立一个超级源点 $S$ 和一个超级汇点 $T$ ，在跑算法之前先看一下每个点是否有不平衡的情况，如果有净流入 $in$ ，则让 $S$ 与当前点连接一条容量为 $in$ 的边；如果有净流出，则让当前点与 $T$ 连接一条容量为 $out$ 的边，这样算上 $S$ 和 $T$ 之后整体还是平衡的。

然后从 $S$ 到 $T$ 跑一遍最大流，此时的 “最大” 是没有意义的，只是借助这个算法找到一组可行解。判断是否可行的条件是刚才连的 $S$ 的那些出边、以及 $T$ 的那些入边是否流满。

有源汇有上下界可行流

这个问题在上一个的基础上加入了指定的源点 $s$ 和汇点 $t$ 。考虑多出来的这个要求，实际上只需要满足源点的流出量恰好等于汇点的流入量即可，因为这两个点不满足流量平衡。所以只需要额外加入一条从 $t$ 到 $s$ 的、容量无穷大的边，然后再按照刚才的方法跑一遍最大流就行了。

有源汇有上下界最大流

先跑一遍可行流来把超级源汇的边流满，然后再跑一遍从 $s$ 到 $t$ 的最大流即可。这不会影响超级源汇的流值。

有源汇有上下界最小流

先跑一遍可行流来把超级源汇的边流满，然后再跑一遍从 $t$ 到 $s$ 的最大流。注意，此时从 $t$ 到 $s$ 的那个多余边容量是无穷大，所以最大流算法总是会优先在这条边上增广。所以必须先删掉这条边才行。

费用流

最小费用最大流

最经典的是最小费用最大流，这个问题是在保证流值最大的情况下，求总费用最小的方案。只需把 Dinic 算法中 BFS 分层的过程改成根据费用跑最短路即可。同时，建反向边时需要保证费用也取相反数。

最小费用（有上下界可行）流

这个问题不等于最小费用最大流，因为总费用最小并不代表着流量最大。实际上，这类费用流的问题大致可以分解成最短路 + 最大流相关问题。比如，最小费用可行流就是在有源汇可行流的基础上，把 BFS 改成最短路。

但是在有负费用的情况下，只能用 Bellman-Ford 这类算法求最短路，它们无法解决图中存在负费用环的情况。这种情况下可以用两条边来等效出一条负费用边。

1. 一条边是原本的边，但是强制它跑满流量。强制的方法就是用有上下界可行流的方法，与超级源汇进行相应的连边。
2. 另一条边是反向边，流量没有额外的限制，但费用变成正的。实际上在正常的建边过程中反向边的费用就应该是相反数，我们只是模拟了这个过程。

Dinic 时间复杂度

• 一般网络：$O(n^{2}m)$，单轮增广复杂度 $O(nm)$
• 各边容量为 $1$ 的网络：$O\left(m\min \left(m^{\frac{1}{2}},n^{\frac{2}{3}}\right)\right)$，单轮增广 $O(m)$
• 单位网络（各边容量为 $1$ 并且除了源汇之外各点入度或出度不超过 $1$）：$O\left(m\sqrt{n}\right)$，单轮增广 $O(m)$