http://chuanwang66.iteye.com/blog/1450715
如果能让每次寻找增广路时的时间复杂度降下来，那么就能提高算法效率了，使用距离标号d（有时候称为“高度h”）的最短增广路算法就是这样的。所谓距离标号 ，就是某个点到汇点的最少的弧的数量（即边权值为1时某个点到汇点的最短路径长度） 。设点i的标号为d[i]，那么如果将满足d[i]=d[j]+1的弧(i,j)叫做允许弧 ，且增广时只走允许弧，那么就可以达到“怎么走都是最短路”的效果 。每个点的初始标号可以在一开始用一次从汇点沿所有反向边的BFS求出，实践中可以初始设全部点的距离标号为0，问题就是如何在增广过程中维护这个距离标号。
Sam评注：
(1).
外国大牛的文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited#1 中有这样一句话非常重要：“We can distance function exactly if each i in V, d[i] equals the length of the shortest path from i to t(sink) in the residual network.”
上面这句话意思是说：只有当d[i]恰好等于i到汇点t的最短路径（边权都为1）时，才称d为“距离函数”。而每次用SAP寻找增广路径初始，d[i] (i∈V)都被初始化为0。因此一开始，只有汇点的距离函数d[t]=0满足这个条件；对其他顶点，d[i]只能称为“i的距离函数值的下界/估计”，因为它<真正的d[i]。于是，外国大牛又冒出这样一句话：
“It is also easy to prove that if d(s)≥|V|, then the residual network contains no path from the source to the sink.”
(2).
寻找一条最短（边最少）增广路径中用到的“递归机制”，实际上保证了最短路径的层次图是从汇点向源点扩展的。而每次用SAP寻找一条增广路径开始时，d[t]=0已经是真正的最短路径，因此如果有最短增广路径，完成SAP搜索后d[i]=真正的最短路径。
(1).
外国大牛的文章http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlowRevisited#1 中有这样一句话非常重要：“We can distance function exactly if each i in V, d[i] equals the length of the shortest path from i to t(sink) in the residual network.”
上面这句话意思是说：只有当d[i]恰好等于i到汇点t的最短路径（边权都为1）时，才称d为“距离函数”。而每次用SAP寻找增广路径初始，d[i] (i∈V)都被初始化为0。因此一开始，只有汇点的距离函数d[t]=0满足这个条件；对其他顶点，d[i]只能称为“i的距离函数值的下界/估计”，因为它<真正的d[i]。于是，外国大牛又冒出这样一句话：
“It is also easy to prove that if d(s)≥|V|, then the residual network contains no path from the source to the sink.”
(2).
寻找一条最短（边最少）增广路径中用到的“递归机制”，实际上保证了最短路径的层次图是从汇点向源点扩展的。而每次用SAP寻找一条增广路径开始时，d[t]=0已经是真正的最短路径，因此如果有最短增广路径，完成SAP搜索后d[i]=真正的最短路径。
主要代码 
- void find_path_sap(int cur){
- ...
- find_path_sap(i);
- ...
- }
维护距离标号的方法是这样的：当找增广路过程中发现某点出发没有允许弧时，将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。这种维护距离标号的方法的正确性我就不证了。由于距离标号的存在，由于“怎么走都是最短路”，所以就可以采用DFS找增广路，用一个栈保存当前路径的弧即可。当某个点的距离标号被改变时，栈中指向它的那条弧肯定已经不是允许弧了，所以就让它出栈，并继续用栈顶的弧的端点增广。为了使每次找增广路的时间变成均摊O(V)，还有一个重要的优化是对于每个点保存“当前弧”：初始时当前弧是邻接表的第一条弧；在邻接表中查找时从当前弧开始查找，找到了一条允许弧，就把这条弧设为当前弧；改变距离标号时，把当前弧重新设为邻接表的第一条弧，还有一种在常数上有所优化的写法是改变距离标号时把当前弧设为那条提供了最小标号的弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。
还有一个常数优化是在每次找到路径并增广完毕之后不要将路径中所有的顶点退栈，而是只将瓶颈边以及之后的边退栈，这是借鉴了Dinic算法的思想。注意任何时候待增广的“当前点”都应该是栈顶的点的终点。这的确只是一个常数优化，由于当前边结构的存在，我们肯定可以在O(n)的时间内复原路径中瓶颈边之前的所有边。
几个重要优化：
1.邻接表优化：
如果顶点多的话，往往N^2存不下，这时候就要存边：
存每条边的出发点，终止点和价值，然后排序一下，再记录每个出发点的位置。以后要调用从出发点出发的边时候，只需要从记录的位置开始找即可（其实可以用链表）。优点是时间加快空间节省，缺点是编程复杂度将变大，所以在题目允许的情况下，建议使用邻接矩阵。
2.GAP优化：
如果一次重标号时，出现距离断层，则可以证明ST无可行流，此时则可以直接退出算法。
3.当前弧优化：
为了使每次找增广路的时间变成均摊O(V)，还有一个重要的优化是对于每个点保存“当前弧”：初始时当前弧是邻接表的第一条弧；在邻接表中查找时从当前弧开始查找，找到了一条允许弧，就把这条弧设为当前弧；改变距离标号时，把当前弧重新设为邻接表的第一条弧。
学过之后又看了算法速度的比较，发现如果写好的话SAP的速度不会输给HLPP。
还有一个常数优化是在每次找到路径并增广完毕之后不要将路径中所有的顶点退栈，而是只将瓶颈边以及之后的边退栈，这是借鉴了Dinic算法的思想。注意任何时候待增广的“当前点”都应该是栈顶的点的终点。这的确只是一个常数优化，由于当前边结构的存在，我们肯定可以在O(n)的时间内复原路径中瓶颈边之前的所有边。
几个重要优化：
1.邻接表优化：
如果顶点多的话，往往N^2存不下，这时候就要存边：
存每条边的出发点，终止点和价值，然后排序一下，再记录每个出发点的位置。以后要调用从出发点出发的边时候，只需要从记录的位置开始找即可（其实可以用链表）。优点是时间加快空间节省，缺点是编程复杂度将变大，所以在题目允许的情况下，建议使用邻接矩阵。
2.GAP优化：
如果一次重标号时，出现距离断层，则可以证明ST无可行流，此时则可以直接退出算法。
3.当前弧优化：
为了使每次找增广路的时间变成均摊O(V)，还有一个重要的优化是对于每个点保存“当前弧”：初始时当前弧是邻接表的第一条弧；在邻接表中查找时从当前弧开始查找，找到了一条允许弧，就把这条弧设为当前弧；改变距离标号时，把当前弧重新设为邻接表的第一条弧。
学过之后又看了算法速度的比较，发现如果写好的话SAP的速度不会输给HLPP。
