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]>=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;

}


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议