网络流

最大流问题

举个例子，互联网上有几台计算机，某些计算机之间建立了一定带宽的有向连接。目标是将数据从某台指定的计算机$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})$