从一个源点 S 到一个汇点 T, 边视为管道, 边权视为管道容量, 网络流就是从 S 点到 T 点的一个可行流

网络流需要满足三个性质:

• 容量限制: 流过一个边的流不超过边的最大容量
• 流量守恒: 除源点汇点以外, 节点的流入流量等于流出流量
• 斜对称性: $F(u,v)=-F(v,u)$ ,退流依赖于此性质

可能会涉及到的炫酷的名词

• 流量
• 容量
• 残量
• 增广路
• 可行流
• 阻塞流
• 最大流
• 残差网络

最大流

求到汇点流量最大的可行流

Ford-Fulkerson 算法

虽然 FF 被称为增广路算法,实际上的目的是让图中不再有增广路

FF 是很多网络流算法的基础,其依赖于增广路定理, 可以记为网络达到最大流当且仅当残留网络中在任何流量调整后也没有可增广路

其过程可以表示为:

• 在残差网络寻找一条增广路
• 增广路的容量都减去最小的那个容量
• 建立反向边, 提供一种类似反悔的机制
• 重复直到没有增广路,此时的残差网络即为最大流

这是一个简单的伪代码

def ford_fulkerson(residual):
  while(True):
    augument_path=get_augument_path_in_residual(residual)
    if not augument_path:
      break
    x=min([w for edge.weight in augument_path])
    for edge in augument_path:
      edge.weight-=x
      edge.weight_rev+=x
  return residual

Edmonds-Karp 算法

FF 是寻找随意一条增广路,这里会导致最终的时间复杂度可能与网络流的大小有关

而将 FF 中的寻找增广路改为寻找最短的增广路(注意这个短与边权无关),与网络流大小无关(显然跑一遍 bfs 即可).时间复杂度为 $O(v\ast e^2)$

这就是 EK 算法的优化点

Dinc 算法

在 bfs 分层图中寻找阻塞流,然后更新残差网络, 周而复始

时间复杂度为$O(v^2\ast e)$

我们可以感性的理解为一个阻塞流很可能是多个增广路的组合,所以不需要每次增广一次,会效率高一些

这里可以多路增广和当前弧优化

最小割

一种割,用于割断最小的边权和使得 S 无法到达 T

最小割等于最大流

费用流

最小费用最大流

定义一条边存在属性单位费用,则流过这条边的费用为单位费用*流量

求在保持流最大的同时，找到总费用最少的可行流

"只要建了反向边，无论增广的顺序是怎样，都能求出最大流。"

所以我们贪心的尝试每次都选择增广费用最少的增广路

那我们把找路的 BFS 换成最短路算法即可,

注意反向边的费用是正向边的相反数

这里我们一般使用 SPFA,因为很可能是个负权图

SPFA 不支持负权回路, 如果有需要可以消圈法

当然 SPFA 是可以被卡成贝尔曼福德得,所以有时候我们得使用迪杰斯特拉求最短路

这个时候为了消去负权需要引入势函数优化

最大费用最大流

对花费取反,然后再对答案取反即可

多源汇

对所有源点建立一个超级源点,汇点建立一个超级汇点, 记容量为无穷

如果需要费用,记费用为 0

上下界

我们不再只关注其流量的上界，而是同时也要关注下界

无源汇上下界可行流

给定一个没有源点和汇点、每条边的流量有上下界的流量网络，问是否存在一种可行流使得流量平衡

现在的约束为

$$C_1(u,v)<=F(u,v)<=C_2(u,v)$$

常规网络流的约束为:

$$0<=F(u,v)<=C_2(u,v)$$

显然要把当前模型转为常规网络流则有:

$$0<=F(u,v)-C_1(u,v)<=C_2(u,v)-C_1(u,v)$$

这样满足了网络流的第一个性质容量限制

那流量守恒和斜对称性?

斜对称性不会因为偏移而改变,但是容量守恒则不一定了

记进出流量分别为为$F_{in},F_{out}$, 则转化为常规的网络流的进出流量为:

$$\begin{gathered} \dot{F_{in}}=F_{in}-\sum C_1(in) \\ \dot{F_{out}}=F_{out}-\sum C_1(out) \end{gathered}$$

这里并不能保证入流边的下界等于出流边的下界

所以我们创建一个源点和一个汇点, 对不平衡的点加入附加边用于平衡流入流出

显然如果是一个可行流, 这些附加边必须流满

因为附加边不是在源点就是汇点,我们可以利用网络流的基本性质判断附加边是否流满

在网络流中最大流显然等于源点流出的最多流量

如果附加边可以流满,此时最大流必然等于附加边之和

所以我们可以求一下现在新的图的最大流,然后判断是否等于源点的附加边之和(或者汇点的,从源点流出显然等于与汇点流入)

有源汇上下界可行流

从汇点到源点连一条下界为 0,上界为 inf 的附加边，得到一张和原图等价的无源汇流量网络，于是转化成了无源汇有上下界可行流问题

有源汇上下界最大流

跑一遍有源汇上下界可行流

接着从原图的定义的源点到汇点跑一遍最大流,然后加上可行流,即为有源汇上下界最大流

有源汇上下界最小流

跑一遍有源汇上下界可行流 接着从原图的定义的汇点到源点跑一遍最大流,然后减去可行流,取反即为有源汇上下界最小流

上下界最小费用可行流

不会