最大流算法----（SAP 和 EK）

　　EK算法的核心
　　反复寻找源点 s 到汇点 t 之间的增广路径，若有，找出增广路径上每一段的最小值delta，若无，则结束。
　　寻找增广路径时用BFS来找，并且更新残留网的值。
　　找到delta后，则使最大流值加上delta，更新为当前最大的最大流值。

　　更详细的到：http://www.cnblogs.com/zsboy/archive/2013/01/27/2878810.html

　　SAP算法
　　1.首先设 h 数组，h[i]表示节点 i 到汇点经过的最少路径数；
　　2.在一次寻找可行路径的过程中，若此时已到达 i 点，对于< i , j >，若h[i]=h[j]+1，则j为可选点，这样可保证每次找到的到达t的路径所经过的边数是最少的；
　　3.某时刻，在到达i处，不存在<i , j>，使得h[i]=h[j]+1,则修改h[i]，设i的所有后继的最小h为t，则修改h[i]=t+1；
　　4.设num[x]为h[]值为x的点的个数。对于一点i，在修改h[i]时，若num[h[i]]=1则停止。因为修改了h[i]，num[h[i]]=0，h[i]的值变大了，没有了大小为h[i]的，出现断层，永远不能到达汇点。

　　算法流程：

　　(1).从源点s开始，找下一个节点p，使得h[s]=h[p]+1，找到继续找p的下一个节点，到达汇点t时转(3)，否则转(2);
　　(2).修改h[s]的值，重新到1；
　　(3).根据本次找到的路径修改路径上的流量和反向边的流量，设最小流量的边为<u,v>，则下一次找路径时，从u开始向汇点找。

　　sap算法详解及模板：http://blog.csdn.net/liguanxing/article/details/5783804

巴特西

最大流算法----（SAP 和 EK）

最新文章

热门文章