SAP算法心得 ~转的吧

网络最大流算法是网络流算法的基础，实现方法很多，但时间复杂度与编程复杂 度难于兼顾。一方面，诸如预流推进等高效算法难于编写调试，有时实际效果欠佳 （参见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]&gt;=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;
}