最大流算法----(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

原文地址:https://www.cnblogs.com/yongren1zu/p/3259976.html