去网上搜了好久，终于找到了一个比较好的模板，为了长远的发展，就把它转到我的博客里来了，呵呵~~~~~
转自：jxy859的专栏
SAP算法 最短增广路算法(Shortest Augmenting Path Algorithm)，是网络流中求最大流的经典算法之一，即每次寻找包含弧的个数最少的增广路进行增广，可以证明，此算法最多只需要进行mn/2次增广。并且引入距离标号的概念，可以在O(n)的时间里找到一条最短增广路。最终的时间复杂度为O(n^2m)，但在实践中，时间复杂度远远小于理论值（特别是加了优化之后），因此还是很实用的。
距离标号：
对于每个顶点i赋予一个非负整数值d(i)来描述i到t的“距离”远近，称它为距离标号，并且满足以下两个条件： 1. d(t)=0 2. 对于残留网络Gf中的一条弧(i,j)，d(i)≤d(j)+1。
允许弧和允许路：
如果残留网络Gf中的一条弧(i,j)满足d(i)=d(j)+1，我们称(i,j)是允许弧，由允许弧组成的一条s-t路径是允许路。显然，允许路是残留网络Gf中的一条最短增广路。当找不到允许路的时候，我们需要修改某些点的d(i)。
Gap优化：
我们可以注意到由于残留网络的修改只会使d(i)越来越大（因为修改前d(i)<d(j)+1，而修改后会存在d(i)=d(j)+1，因此变大了），所以说d(i)是单调递增的，这就提示我们，如果d函数出现了“断层”，即没有d(i)=k，而有d(i)=k±1，这时候必定无法再找到增广路径。我们可以这么想，现在的i满足d(i)=k+1，发现没有一个d(j)为k，因此就会尝试去调整d(i)，但是d(i)是单调递增的，只会越来越大，所以k这个空缺便永远不会被补上，也就是说无法再找到增广路径。
当前弧优化：
可以注意到一个事实：如果说在某次迭代中从i出发的弧(i,j)不是允许弧，则在顶点i的标号修改之前(i,j)都不可能是允许弧。（因为d(i)不变，d(j)不减且d(i)<d(j)+1）这样，在查找允许弧的时候只需要从上一次找到的允许弧开始找。所以我们增加“当前弧”这个数据结构，记录当前顶点找到的允许弧，只有在修改这个顶点标号时才会更改这个顶点的当前弧。