网络流问题

1. 基本模型

一个网络是一张有向图 $G=(V,E)$，对于每条有向边 $(u,v)\in E$ 存在容量限制 $c(u,v)$，当 $(u,v)\not\in E$ 时，$c(u,v)=0$。网络的可行流分为有源汇（指定了两个节点 $s,t$，代表图的源点和汇点）和无源汇。

在一张网络上，流函数 $f:V^2\rightarrow \mathbb R$，$f(x,y)$ 代表边 $x\rightarrow y$ 的流量，满足：

1. $f$ 满足容量限制：$f(x,y)\le c(x,y)$，当两者相等时，$x\rightarrow y$ 就流满了；
2. 斜对称性质：$f(x,y)=-f(y,x)$，这是为了方便反悔。
3. 流量守恒：除源点和汇点外（无源汇则无这个性质），从每个节点流入和流出的流量相等，即 $\forall i\ne s,t,\sum f(u,i)=\sum f(i,v)$，也就是说，每个节点不储存流量，进去多少就流出来多少。

下面是一些定义：

• 对于有源汇，有 $\sum f(S,i)=\sum f(i,T)$，此时这个相等的和称为流函数 $f$ 的流量。
• 定义流 $f$ 在网络 $G$ 上的残量网络 $G_f=(V,E_f)$，其残量容量为 $c_f=c-f$。删掉满流边之后即得到残量网络。
• 对于有源汇，定义增广路 $P$ 是残量网络 $G_f$ 上源点到汇点的一条路径。
• 将点集分为两个互补相交的 $A,B$，且满足 $S\in A, T\in B$，这种划分方式称为割，割的容量为 $\sum_{u\in A}\sum_{v\in B}c(u,v)$，流量为 $\sum_{u\in A}\sum_{v\in B}f(u,v)$。如果 $u\in A,v\in B$，那么 $(u,v)$ 是割边，可以看出，割边一般不止一条。

2. 网络最大流

2.1 增广

我们寻找网络上的一条增广路 $P$！在这条增广路上给每条边增加 $c_f(P)=\min\{c(u,v)\mid (u,v)\in P\}$ 的流量，来构建新的流函数，并注意这个过程要满足斜对称，即对于反向边减去 $c_f(P)$ 的流量。

想象当流量流过反向边 $(v,u)$ 时，实际是在和原来流过这条边的流量的对冲，以保证流量守恒。实际上如果这条边不存在，则永远不会有水流顺流流过 $(v,u)$。

2.2 最大流最小割定理

想要证明这个做法是正确的，我们需要证明：当增广路不存在时，就已经得到最大流。

（待补充）

同时这说明了一个事情：最大流支持动态加边，如果加边导致出现了新的增广路，那么只需要继续尝试增广就可以了。

2.3 Edmonds-Karp

相当于不断寻找长度最短的增广路。

（待补充）

注意实现时，我们并不会去记录流函数，这样有点浪费，而是直接修改容量限制。反向边的负流量相当于增加反向边的容量限制，流过的流量相当于减少正向边的容量限制。

（待补充）

2.4 Dinic

2.5 无负环费用流