集大成与一体，最终确定为SAP算法

wolong

　　网络最大流算法是众多网络流的基础，实现的办法很多，但是在时间复杂度和编程复杂度方面，却总是很难做到两者尽美。
　　比如目前最牛B的高标推进算法(前我前面日志)，编程起来居然可以长达接近200行代码，有时候效果还不是很让人满意。
　　另一方面，简单的寻找增广路算法时间上却不敢恭维。所以很多人都选用Dinic算法。
　　其实！SAP算法综合起来说，时间复杂度很低，编程很简单，而且很易于理解，我觉得，没有比SAP更好的最大流算法了。
　　SAP算法框架：
　　1、定义距离标号为各点到汇点距离的下界(即最短距离)。
　　2、在初始距离标号的基础上，不断沿着可行弧找增广路。可行弧的定义为{( i , j ) , h[ i ]==h[ j ]+1 };
　　3、遍历当前节点完以后，为了保证下次再来的时候有路可走，重新标号当前距离。
　　h[ i ] = min（h[ j ] +1）；
　　4、检查重新标记的顶点，若其为原点，且被标记的高度等于节点个数时，图中已经不存在增广路，算法可结束。否则继续从原点开始遍历
　　别人的一些心得：
　　1、理论上初始标号要用反向BFS求得，实践中全部设为0，这样做几乎不改变实践复杂度。
　　2、GAP常数优化！（性价比极高）
　　     由于我们不停的遍历，最大流很可能便早就已经求出来了。那么我们接下来的遍历便成了无用功。可以发现，距离标号是连续单调变化的。如果某一种大小标号的节点数量为零。也就是出现了不连续，断层！那么图中也不肯能再存在增广路了。实践中，我们用一个vh[ i ]数组用来记录标号为i的顶点的个数，若重标号使得vh数组中的原标号数目变为了0，那么就停止算法。
　　
　　附上一张别人测试出的效率比较表，让大家可以更直观的看到SAP算法的优势

　　PS：高标推进虽然快一点，不过代码量上实在是多，可以见我前面的日志
　　下面帖上自己的SAP代码
　　邻接表是必须的


View Code


1 struct node
2 {
3     int v;
4     int f;
5     int w;
6     struct node *next;
7 };
8
9 node *link[500];
10 node edge[10000];
11 int num;
12
13 void add(int u,int v,int f,int w)
14 {
15     edge[num].w=w;
16     edge[num].v=v;
17     edge[num].f=f;
18     edge[num].next=link;
19     link=edge+num++;
20     edge[num].w=-w;
21     edge[num].v=u;
22     edge[num].f=0;
23     edge[num].next=link[v];
24     link[v]=edge+num++;
25 }
　　
　　


View Code


int find(int u,int FLOW) //FLOW是总流量
{
         if(T==u)
                   return FLOW;
         int left=FLOW; //left是剩余流量
int f;
         int temp=n-1;
         for(node *p=link;p;p=p->next)
         {
            int res=p->f-flow[p->v]; //计算该边剩余的可行流量
if(res && h==h[p->v]+1)  //满足可行弧条件
              {
                     int MIN=min(res,left);  //计算最小可行流量
                        f=find(p->v,MIN);  //递归寻找增广路
                        left-=f;
                     flow[p->v]+=f;
                     flow[p->v]-=f;
                     if(!left || h[S]==n)
                             return FLOW-left; //总流量减去剩下的流量=流去的流量
              }
             res=p->f-flow[p->v];
             if(res && h[p->v]<temp)
                     temp=h[p->v];
         }
         if(left==FLOW) //需要重新标记
           {
             vh[h]--;  //重标记以后，原标记的数目肯定减少了一
if(!vh[h]) //出现了断层，已经找到了最大流，停止算法
               {
                 h[S]=n;
              }
              else
              {
                 h=temp+1;
                 vh[h]++;
              }        
         }
         return FLOW-left;
}

void sap()
{
         int ans=0;
         n=T+1;   //S->T 有T+1个点
          memset(vh,0,sizeof(vh));  //常数优化数组
          memset(h,0,sizeof(h));
         memset(flow,0,sizeof(flow));
         vh[0]=n;  //标号为0的顶点有n个~~
while(h[S]<n)
         {
                   ans+=find(S,inf);
         }
         cout<<ans<<endl;
}