网络流

最大流问题

举个例子, 互联网上有几台计算机, 某些计算机之间建立了一定带宽的有向连接。目标是将数据从某台指定的计算机$s$ (称为源点) 传输到$t$ (称为汇点) , 求单位时间内最多能传输多少数据。

有许多类似的问题, 都可以抽象成类似的网络流问题, 上面的问题是一个 (单源单汇) 最大流问题。形式化地描述, 即为:

对无重边与自环的有向图$G(V,E)$, 若每条边$e\in E$有一个权值$w_e$ (称作该边的容量) , 且$s\in V,t\in V$, 称该图为一个网络。若一个有向图$G'(V,E)$满足: $G'$$G$完全相同, 除去每条边$e\in E$有另一个权值$f_e$ (称作该边的流量) 以外; 并且对$\forall u\in V,u\ne s,u\ne t$满足$\sum\limits_{e=\langle u,v\rangle}{f_e}=\sum\limits_{e=\langle v,u\rangle}{f_e}$ (即流入每个顶点的流量等于流出的流量) , 那么称该有向图$G'$为网络$G$上的一个流, 该流的流量$f$定义为$\sum\limits_{e=\langle s,u\rangle}{f_e}$。一个网络的最大流是指该网络的所有流中流量最大的那个。

通常在不引起歧义的情况下, 并不区分最大流最大流的流量

对上面的抽象模型, 解决最大流问题的算法有两类: 增广路算法和预流推进算法。最常用的是增广路算法中的 Ford-Fulkerson 算法和​ Dinic​ 算法。这里将常见的算法罗列如下:

算法名 算法分类 复杂度
Ford-Fulkerson算法 增广路 $O(FE)$
Dinic算法 增广路 $O(n^2m)$
HLPP (我也不会) 预流推进 $O(n^2\sqrt{m})$