在开始之前，先阐述距离标号的定义。后文中距离标号有两个定义，故此明确：

①在最大流部分，u点距离标号du定义从源点（或汇点）开始BFS第一次搜到u点的时间（即为经过的最少边数）

②在费用流部分，u点距离标号du定义为源点（或汇点）到u点的最短路径（将边的费用视为距离）

形式化的定义，对于任何点u，v∈V有du<=dv+w(v,u)（性质1），并且至少有一个点v可以使等号成立（性质2）。将使du=dv+w(v,u)的边(v,u)称为可行边。在最大流部分，w(v,u)即为1（如果边(v,u)存在）；在费用流部分w(v,u)即为边(v,u)的费用c（如果边(v,u)）存在。

                                                I、最大流

                                                     -----------只是一个引子

还记得EK、dinic、ISAP么？。

求网络中最大流的算法有两个体系：增广路系和预流推进系。增广路系的核心就是不断地寻找增广路直到网络中不再存在增广路，而增广路系算法的变化只是在于如何找增广路。

EK：每次用广搜寻找一条最短的增广路（即包含最少的边），然后沿其增广。

                                         ↓

dinic：同样是寻找一条最短的增广路，但是并不需要每次都广搜。EK算法每次广搜所获得的信息并没有被完全利用，因此dinic将其改进，用广搜获得每个点到源点的距离标号，增广时沿距离标号严格减1的路径增广，直到网络中不再存在这么一条路径，那么重新广搜计算距离标号，如果广搜发现整个源点到汇点已经不连通那么退出算法。

                                         ↓

ISAP：与dinic一样基于距离标号，不过这里保存的是到汇点的距离标号。并且考虑每次增广对网络的影响，发现增广只会使点的距离标号变大，并且并不会破坏距离标号的性质1，只会破坏性质2。找不到可行边就是因为性质2被破坏。那么重新修补性质2的方法也很简单，并不需要重新计算整个图的距离标号，只需要调整距离标号：如果从u点开始寻找增广路没有成功，即u点的距离标号的性质2被破坏，那么在所有<u,v>（v∈V）中找到距离标号最小的一个v，使du=dv+1即可。

                                             II、最小费用最大流

                                                      -----------真正的东西

算法I：最小费用最大流一般使用的是基于SPFA的增广路算法，即每次用spfa计算图的距离标号，然后沿着可行边进行增广。

                                         ↓

算法II（原始对偶算法）：根据最大流和费用流算法的对应，这里应该存在一个类dinic算法，即并不每次都用spfa重新计算整个图的距离标号，而是在图中不再存在由可行边组成的增广路时再进行一次SPFA重新计算点的距离标号，如果源点与汇点不再连通那么退出算法。这个算法因为dinic算法的存在而变得显然。然后有一个优化，即只有在第一次计算距离标号时用spfa，之后对距离标号的修正可以在对边重赋权之后dijkstra做。

                                         ↓

算法III（zkw费用流）：zkw费用流算法可以视为ISAP算法在费用流问题上的映射算法。这里距离标号同样记录的是到汇点的。每次增广，同样不会破坏距离标号的性质1，只会破坏性质2。并且被破坏的点并没有很多（只有在增广路上的点有可能被破坏）。因此并不需要SPFA来重新计算全部的距离标号。如果某一次寻找可行边组成增广路的尝试进行到点u失败，那么在所有的边<u,v>（v∈V）中找到距离标号最小的一个v，使du=dv+c<u,v>即可。

                                            III、最小费用最大流的算法分析

算法I和EK算法是如此的类似，不妨称其为E'K'算法。算法II因为介于算法I与算法III中间，不予评价。称算法III为zkw算法。

zkw本人是这么说的：

这里（E'K'算法-----zkw算法的比较）与（EK算法-------ISAP算法的比较）完全相同，产生差异的原因也相同。举个例子，如果一个网络最大的可能流量只有2，那么判断此网络的最大流到底是多少，EK算法就会快于ISAP算法。

考虑到ISAP完全碾压EK算法，zkw算法也是可以碾压E'K'算法的。

                                            IV、最小费用流算法的优化

                                                         ---------------照葫芦画瓢，形似也就能神似

这里我们试图加快zkw算法的速度。

在求解最大流问题中，常见的对ISAP算法的优化有：当前弧优化、多路增广、gap优化与程序开始执行时的一次BFS来直接给各点确定一个距离标号。

那么如果迁移到最小费用最大流问题中，当前弧优化显然还是能用的，因为一条边有可能沿其增广多次；多路增广也能用；而程序开始执行时先计算一次各点的距离标号也是合理的，但是gap优化在最小费用最大流中就不能用了。