网络流学习笔记

这个必须写。

先梳理一下，到时候再整理，证明先简写或者跳过。

流网络：一个有向图，每条边有一个容量，有一个源点 \(s\) 和一个汇点 \(t\)。每条边有一个属性称为容量，如果把流网络抽象成水管的话，那么边的容量就是每根水管的每秒最大承受的进水量。每条边也有一个流量，这个值大于等于 \(0\) 且小于等于容量，相当于每根水管的实际进水量。（不考虑反向边）

抽象成源点源源不断的向流网络里面流水，通过中间的边最终流到汇点的过程。

对于一个可行流（不考虑反向边），每条边都需要满足两个条件：

• 容量限制：流量大于等于 \(0\) 且小于等于容量

• 流量守恒：对于除了源点和汇点的所有点，必须满足进去的流量等于出去的容量。相当于中间的点上不会留着水，只有源点在源源不断地流出，汇点在源源不断地进水。

满足上述条件的一组原流网络的流量 \(f\)，称之为原网络的可行流。

定义可行流的流量为从源点流出的流量减去流入源点的流量（其实就是净流出的流量）。

最大流：指的就是最大可行流。

引入一个残留网络的概念：残留网络是通过原网络的一个可行流决定的。它的点集和原网络相同，边集不仅包含了原网络的所有边，还包含了原网络的所有边的反向边。其中和原网络方向相同的边的容量等于原网络中该边的容量减去该边在当前可行流中的流量（也就是该边还能再增加的流量），和原网络反向的边的容量等于该边在当前可行流中的流量（也就是该边还能再减少的流量）。

注意：只有在残留网络中才考虑反向边！

有一个很重要的性质：原网络的一个可行流加上这个可行流对应的残留网络的一个可行流还是原网络的一个可行流。其中两个可行流相加是指加上同向边，减去反向边。并且得到的新的可行流的流量等于原可行流流量加上残留网络可行流流量。

这个性质使我们发现，如果残留网络中存在一个流量大于 \(0\) 的可行流的话，那么原网络中的那个可行流一定不是最大流，因为还可以加上残留网络中的可行流的流量（大于 \(0\)）使得原网络的流量更大。

因此又会引出一个新的概念，增广路。增广路是指在残留网络中，一条从源点 \(s\) 到汇点 \(t\) 的路径，满足路径上经过的每一条边的容量大于 \(0\)。显然，如果存在增广路的话，那么一定也存在流量大于 \(0\) 的可行流，这又说明了原网络的当前可行流不是最大流。