个人觉得该算法细节比较多，大多数人（包括我）写的就是一坨大便，所以参考论文给出简略的一些描述。。有错误感谢指出！

• http://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf
• http://i.stanford.edu/pub/cstr/reports/cs/tr/94/1523/CS-TR-94-1523.pdf

基本上按照第一篇的伪代码写就可以了。。然后读第二篇里的一些内容

网络 $G=(V,E,c,f,s,t,e)$ ， $c:E\to\mathbb{R}$ 容量函数，$f:E\to\mathbb{R}$ 流量函数。

距离标号 $d:V\to\mathbb{N}$ 。

溢出函数 $e:V\to\mathbb{R}$ 。

1. 从汇 $t$ 反向 BFS 计算准确的距离标号
2. 从源 $s$ 往所有相邻的点满流送出去（即流量等于容量，这些溢出的点都标记为活跃）
3. 开始从最大标号的活跃点处理（即 推送/重贴标签 选择其一进行）

$d(s)=\vert V\vert$ ， $d(t)=0$

然后将这个算法分为 2 个部分，第一部分，我们处理 $d(v)\lt \vert V\vert$ 的，可以想象成水从高处往低处流，水不可能逆流！所以最后可以得到最大流的值，但此时网络并不能满足一些约束。在第一篇论文中有证明， $d(v)$ 最大可能为 $2\vert V\vert -1$ 。第二部分从 $s$ 反向 BFS 计算距离标号，因为我们要把多余的流送回 $s$ ，使得最后的剩余网络是正确的且满足约束。

几个注意的点就是首先不能使用优先队列，要使用他给的数构即链表的数组，因为我们要让每次删除都是 $O(1)$ 才行，这和不饱和推送的次数有关，会影响复杂度（第一篇论文有提）。然后需要用当前弧，这论文里这样写的，有一篇论文说没有用当前弧证明了复杂度啥的，我就看了标题没看内容不知道说的具体是啥，但是如果有人不想用当前弧，那可能需要自己写证明才行了（否则也太扯淡了）！

关于优化：

gap 优化可以将一些不能到的点提前标记为 $d(v)=\vert V\vert$ 。

global 重贴标签周期性执行，这个周期选择需要使得其不能成为复杂度瓶颈才行，第二篇论文中给出的是 $\vert V\vert$ 次重贴标签后进行，注意第一部分和第二部分的起点不同，因为第二部分没必要再往 $t$ 推了。

提前说一下我也不会写这些！但是我会写没有任何优化的，就抄伪代码，反正证明论文里有，抄伪代码谁都会，但是实在看不下去有人自己改东西又不给出河里说明的。