最大流

一些定义

1. 流网络：有向图，没有反向平行边，源点$s$和汇点$t$分别只有一个

2. 流：一个实值函数$f: V\times V \rightarrow \mathbb{R}$，并且满足以下两条性质：

   1. 容量限制：$0 \le f(u, v) \le c(u, v)$
   2. 流量守恒：$\sum_{v\in V}f(u, v) = \sum_{v\in v}f(v,u)$

   最大流问题中，我们想找到最大的$f(s,t)$

两个简单的推广

1. 如果有反向平行边呢？

   很简单，本来是u->v, v->u，现在添加一个结点u'，把图转化为u->v, v->u', u'->u，就去掉了反向平行边

2. 如果有多个源和汇呢？

   也不难，添加一个超级源和超级汇，从其出发的有向边指向真实的源点，并且容量无限大；汇点同理。

Ford-Fulkerson方法的准备

1. 残存网络$G_f$：给原图添加反向平行边，其容量和正向边的流一样大。原图的正向边容量改为其原容量与流的差（如果为算出新的容量为0，那么就认为这个边不存在），这样一操作，得到的就是所谓的残存网络$G_f$。

   更正式地：

   $$c_f(u, v) = \begin{cases} c(u, v) - f(u, v) & (u,v)\in E \\ f(u, v) & (v,u)\in E \\ 0 & \text{Otherwise} \end{cases}$$

   反向边的存在使得我们在需要的时候可以反向推流，也就是所谓抵消操作，来达到全局最优解。

2. 增广路径：残存网络中从源点到汇点的一条简单路径。易知

   $$\displaystyle c_f(p) = \min_{(u,v)\in p}c_f(u, v)$$

3. 找到一条增广路径，我们据此增加原图中的流，然后再更新残存网络$G_f$。这作为一次增广操作。

4. 流网络的切割：将网络的结点分为两个集合$S$和$T$，其中$s \in S$且$t\in T$，并且$S + T = V$（此式蕴含了$S$、$T$不相交）

5. 横跨切割的净流量：连接$S$、$T$的边的流量的和。（如果是反流回来的，那么要加个负号）

6. 切割的容量：连接$S$、$T$的边的容量和

根据上面的定义，可以推得最大流最小割定理，也就是最大流的大小和最小的切割容量相等。更具体地，下面三个结论等价：

1. $f$是$G$的最大流
2. $G_f$没有增广路径
3. $\vert f\vert = c(S, T)$

Ford-Fulkerson方法

简单来说：一直增广，直到无法增广，最终得到的就是最大流，同时也是最小割。

算法的正确性可以通过最大流最小割定理直接得出。算法的复杂度分析在此略去。

Edmonds-Karp算法

简单来说，每次沿着最短路增广。也就是使用广度优先搜索增广。

算法的正确性是显然的。时间复杂度为$O(VE^2)$，不过我感觉这个上界很松。

关于时间复杂度的分析这里暂时略过，以后再填坑。

EK算法虽非最优，但已足以对付绝大多数情况。

Dinic算法

比EK算法多了一点点东西，并不很复杂。算法分成两个阶段：

1. BFS分层：一个结点的层树是其到$s$的最短距离
2. DFS增广。增广有条件，每次只找比当前结点高度函数多1的结点进行增广，确保增广路最短

复杂度$O(V^2E)$

两个优化

1. 多路增广：找到一条增广路之后，如果增广容量没有用尽，那么利用残余容量再找一条增广路
2. 当前弧优化：如果一条边已经被增广过，那么就不必对其增广第二次。

Push-Relabel方法

1. 预流：与普通的流相比，允许结点「存储」一定的流。如果对于一个结点，其流入的流比流出的流多，则称该结点溢出。（如果没有结点溢出，那么预流就是流。）

2. 高度函数$h(v)$：$h: V \to \mathbb{N}$，满足

   1. $h(s) = \vert V\vert$
   2. $h(t) = 0$
   3. $\forall(u,v)\in E_f, h(u) \le h(v) + 1$

   高度还是就是push-relabel方法需要一直维护的量。

3. 两个基本操作

   1. Push：如果结点$u$溢出，则将超额流推送到$u$的邻接结点（$h(u) = h(v) + 1$且$c(u,v)-f(u,v)\gt 0$）
   2. Relabel：如果结点$u$溢出，且$h(u) \le h(v)$，则将$h(u)$更新为$\displaystyle \min_{(u,v)\in E}h(v) + 1$

Push-relabel方法正确性的证明，关键在于充分利用高度函数$h$的性质。以及残存网络与流网络的关系。

通用预流推进算法

有了上面的准备，便可以引入push-relabel方法（通用预流推进算法）

1. 初始化 $$f(u,v) = \begin{cases}c(u, v) & u = s\\ 0 & u\ne s\end{cases}$$

   $$h(u) = \begin{cases}\vert V\vert & u = s \\ 0 & u \ne s\end{cases}$$

2. 选择结点进行Push和Relabel，直到所有结点都不溢出为止。

HLPP算法（最高标号预流推进算法）

1. 初始化
2. 选择溢出结点高度最高的结点，并对其进行Push
3. 如果仍然溢出，则relabel，回到步骤2
4. 如果没有溢出结点，算法结束

复杂度$O(V^2\sqrt{E})$

两个优化

1. BFS优化：初始化$h(u)$为$u$到$t$的最短距离
2. GAP优化：如果$h(u)=t$的结点个数为0，那么$h(u) \lt t$的结点永远无法推送超额流到$t$。因此，就将超额流送回$s$。（将高度变成$n+1$，以尽快推回$s$。