网络流算法学习笔记

屈婉玲《算法设计与分析》第2版第7章网络流算法学习笔记。

最大流问题，相当于有从s到t的供水系统，每段路径都有限定流量，除了s、t两地外，每个中间点都不能滞留，从s流入多少，就从t流出多少。求该网络能承载的最大流量。

容量网络：N。连通图N=

容量：c(i, j)。每条边有一个非负实数c(i, j)代表边的容量

简单容量网络：边的容量均为1，所有中间点要么入度为1要么出度为1

发点/源点：s

收点/汇：t

中间点：除发点、收点外的顶点

可行流：f。设f：E->R*（非负实数集），f(i, j)表示从i到j的流量。满足：

当找不到s-t增广链（最后一次循环）时，获得标号的顶点组成A，未获得标号的顶点组成Ã，(A, Ã)即为最小割集。

以图7.2为例，模拟FF算法流程：

输入：第一行输入节点数N（从0到N-1编号，0为发点，N-1为收点）和边数M；接下来M行，每行给出一条边，用i j 容量描述，输入样例如下： 6 9 0 1 8 0 2 12 1 3 6 1 4 10 2 1 2 2 3 10 3 5 8 4 3 2 4 5 10

输出：最大流f(i, j)，用i j 流量描述；接下来一行打印发点发出的总流量；接下来两行分别输出最小割集A的顶点，和Ã的顶点。输出样例如下： Maximum flow: 0 1 8 0 2 10 1 3 0 1 4 10 2 1 2 2 3 8 3 5 8 4 3 0 4 5 10 Total flow: 18 Minimum cut: 0 2 3 1 4 5