网络最大流算法是网络流算法的基础，实现方法很多，但时间复杂度与编程复杂度难于兼顾。一方面，诸如预流推进等高效算法难于编写调试，有时实际效果欠佳（参见dd_engi的评测）；另一方面，基于增广路的算法大多时间效率不高。于是许多人选择了相对简单的Dinic算法。事实上，SAP算法更易于理解，时间效率更高，编程更简单，思路更清晰。（名词解释）SAP（Shortest Augmenting Paths）: 最短增广路

 

 

算法基本框架：

·  定义距离标号为到汇点距离的下界。

·  在初始距离标号的基础上，不断沿可行弧找增广路增广，一般采用深度优先。可行弧定义为:

                                 {(i, j) | h[i] = h[ j]+1}

·  遍历当前节点完成后，为了使下次再来的时候有路可走（当然要满足距离标号的性质：不超过真实距离），重标号当前节点为:

                                 min {h[ j]| (i, j )}+1

·  重标号后当前节点处理完毕。当源点被重标号后，检查其距离标号，当大于顶点数时，图中已不存在可增广路，此时算法结束；否则再次从源点遍历。

·  理论复杂度为:

                                 O(n2m)

我的心得：

·  理论上初始标号要用反向BFS求得，实践中可以全部设为0，可以证明：这样做

不改变渐进时间复杂度。

·  理论上可以写出许多子程序并迭代实现，但判断琐碎，没有层次，实践中用递归简单明了，增加的常数复杂度比起SAP速度微乎其微却极大降低编程复杂度，易于编写调试。

·  ★GAP优化★ （性价比极高，推荐！详见程序“//GAP”部分）

注意到我们在某次增广后，最大流可能已经求出，因此算法做了许多无用功。可以发现，距离标号是单调增的。这启示我们如果标号中存在“间隙”，则图中不会再有可增广路，于是算法提前终止。实践中我们使用数组vh[i]记录标号为i的顶点个数，若重标号使得vh中原标号项变为0，则停止算法。


#include <cstdio>

#include <cstring>

const int MAXN=201,INF=(1<<31)-1;

int c[MAXN][MAXN];   //残留网络

int d[MAXN],vd[MAXN];  //d[]:距离标号, vd[]:标号为i的结点个数

int n,m,flow;

void init()

{

 scanf("%d%d",&m,&n);

 for(int i=1;i<=m;i++)

 {

  int j,k,wt;

  scanf("%d%d%d",&j,&k,&wt);

  c[j][k]+=wt;

 }

}

int Min(int a,int b) {return a<b?a:b;}

int aug(int i,int augco)   //i:顶点, augco:从i为起点的最大增广容量    

{

 int j, augc = augco, mind = n-1, delta;

 if(i==n)       //到达汇点

   return augco;

  for(j = 1;j <= n; j++) //枚举i的邻接点

  if(c[i][j]>0)    //如果有边到j 

  {

   if(d[i]==d[j]+1)  //(i,j)为可进入弧

   {

    delta = min(augc,c[i][j]);  //求出经(i,j)的可增广最大值

    delta = aug(j,delta);       //递归增广，返回沿(i,j)的实际增广量

    c[i][j] -= delta;   //更新残留网络

    c[j][i] += delta;   

    augc -= delta;    //augc记录剩下的需要增广的量

    if(d[1]>=n)     //结束，向上一层返回经过i的实际增广量

     return augco-augc;

    if(augc == 0) break;        //已经到达可增广上界，提前跳出

   }

   if (mind<d[j])  mind = d[j];    //更新最小的邻接点标号

  }

 if(augco==augc)                         //如果从i点无法增广

 {

  vd[d[i]]--;       //标号为d[i]的结点数-1

  if(vd[d[i]] ==0 )     //GAP优化

      d[1] = n;

  d[i] = mind + 1;     //更新标号

  vd[d[i]]++;       //新标号的结点数+1

    }

 return augco-augc;   //向上一层返回经过i的实际增广量     

}

void sap()

{

 memset(d,0,sizeof(d));

 memset(vd,0,sizeof(vd));

 vd[0] = n;

 while(d[1] < n)

  flow+=aug(1,INF);

}

int main()

{

 init();

 sap();

 printf("%d\n",flow);

 return 0;

}