最大流
常用的算法: Edmond-Karps 和 Dinic
无源汇有上下界可行流
首先明确问题:现在这个问题叫做 “可行流” 而不是 “最大流”,是因为现在有了额外的每条边流量上下界的要求,所以未必存在一个流满足所有这些条件。
假设一条边的流量下界是 、上界是 ,则基本的想法是先固定让这条边流过 ,然后剩下的 放在算法里跑。但是如果直接把这个边的流量预先设为 ,建好的图不一定满足对于每个点都有流出等于流入。
解决方法是建立一个超级源点 和一个超级汇点 ,在跑算法之前先看一下每个点是否有不平衡的情况,如果有净流入 ,则让 与当前点连接一条容量为 的边;如果有净流出,则让当前点与 连接一条容量为 的边,这样算上 和 之后整体还是平衡的。
然后从 到 跑一遍最大流,此时的 “最大” 是没有意义的,只是借助这个算法找到一组可行解。判断是否可行的条件是刚才连的 的那些出边、以及 的那些入边是否流满。
有源汇有上下界可行流
这个问题在上一个的基础上加入了指定的源点 和汇点 。考虑多出来的这个要求,实际上只需要满足源点的流出量恰好等于汇点的流入量即可,因为这两个点不满足流量平衡。所以只需要额外加入一条从 到 的、容量无穷大的边,然后再按照刚才的方法跑一遍最大流就行了。
有源汇有上下界最大流
先跑一遍可行流来把超级源汇的边流满,然后再跑一遍从 到 的最大流即可。这不会影响超级源汇的流值。
有源汇有上下界最小流
先跑一遍可行流来把超级源汇的边流满,然后再跑一遍从 到 的最大流。注意,此时从 到 的那个多余边容量是无穷大,所以最大流算法总是会优先在这条边上增广。所以必须先删掉这条边才行。
费用流
最小费用最大流
最经典的是最小费用最大流,这个问题是在保证流值最大的情况下,求总费用最小的方案。只需把 Dinic 算法中 BFS 分层的过程改成根据费用跑最短路即可。同时,建反向边时需要保证费用也取相反数。
最小费用(有上下界可行)流
这个问题不等于最小费用最大流,因为总费用最小并不代表着流量最大。实际上,这类费用流的问题大致可以分解成最短路 + 最大流相关问题。比如,最小费用可行流就是在有源汇可行流的基础上,把 BFS 改成最短路。
但是在有负费用的情况下,只能用 Bellman-Ford 这类算法求最短路,它们无法解决图中存在负费用环的情况。这种情况下可以用两条边来等效出一条负费用边。
- 一条边是原本的边,但是强制它跑满流量。强制的方法就是用有上下界可行流的方法,与超级源汇进行相应的连边。
- 另一条边是反向边,流量没有额外的限制,但费用变成正的。实际上在正常的建边过程中反向边的费用就应该是相反数,我们只是模拟了这个过程。
Dinic 时间复杂度
- 一般网络:,单轮增广复杂度
- 各边容量为 的网络:,单轮增广
- 单位网络(各边容量为 并且除了源汇之外各点入度或出度不超过 ):,单轮增广