终于决定开始学习网络流了=.=

<<图论算法理论、实践与应用>>那本书讲了很多关于求最大流的算法，然后我就只挑了一种传说中神奇的SAP算法学习。

首先引入几个新名词：

1、距离标号：

所谓距离标号 ，就是某个点到汇点的最少的弧的数量（即边权值为1时某个点到汇点的最短路径长度）。

设点i的标号为level[i]，那么如果将满足level[i]=level[j]+1的弧(i,j)叫做允许弧 ，且增广时只走允许弧。

2、断层（本算法的Gap优化思想）：

gap[i]数组表示距离标号为i的点有多少个，如果到某一点没有符合距离标号的允许弧，那么需要修改距离标号来找到增广路；

如果重标号使得gap数组中原标号数目变为0，则算法结束。

SAP算法框架：

1、初始化；

2、不断沿着可行弧找增广路。可行弧的定义为{( i , j ) , level[i]==level[j]+1};

3、当前节点遍历完以后，为了保证下次再来的时候有路可走，重新标号当前距离，level[i]=min(level[j]+1);

该算法最重要的就是gap常数优化了。

下面对hdu 1532贴上模版：

邻接矩阵：

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 #define MAXN 222 6 #define inf 100000000+1000 7 int map[MAXN][MAXN];//存图 8 int pre[MAXN];//记录当前点的前驱 9 int level[MAXN];//记录距离标号10 int gap[MAXN];//gap常数优化11 int NV,NE;12 13 //入口参数vs源点，vt汇点14 int SAP(int vs,int vt){15     memset(pre,-1,sizeof(pre));16     memset(level,0,sizeof(level));17     memset(gap,0,sizeof(gap));18     gap[0]=vt;19     int v,u=pre[vs]=vs,maxflow=0,aug=inf;20     while(level[vs]
         
          0&&level[u]==level[v]+1){24                 break;25             }26         }27         if(v<=vt){28             pre[v]=u;29             u=v;30             if(v==vt){31                 aug=inf;32                 //寻找当前找到的一条路径上的最大流  33                 for(int i=v;i!=vs;i=pre[i]){34                     if(aug>map[pre[i]][i])aug=map[pre[i]][i];35                 }36                 maxflow+=aug;37                 //更新残留网络38                 for(int i=v;i!=vs;i=pre[i]){39                     map[pre[i]][i]-=aug;40                     map[i][pre[i]]+=aug;41                 }42                 u=vs;//从源点开始继续搜43             }44         }else {45             //找不到可行弧46             int minlevel=vt;47             //寻找与当前点相连接的点中最小的距离标号48             for(v=1;v<=vt;v++){49                 if(map[u][v]>0&&minlevel>level[v]){50                     minlevel=level[v];51                 }52             }53             gap[level[u]]--;//(更新gap数组）当前标号的数目减1；54             if(gap[level[u]]==0)break;//出现断层55             level[u]=minlevel+1;56             gap[level[u]]++;57             u=pre[u];58         }59     }60     return maxflow;61 }62 63 int main(){64     int n,m,u,v,cap;65     while(~scanf("%d%d",&m,&n)){66         memset(map,0,sizeof(map));67         for(int i=1;i<=m;i++){68             scanf("%d%d%d",&u,&v,&cap);69             map[u][v]+=cap;70         }71         printf("%d\n",SAP(1,n));72     }73     return 0;74 }75 76 77             78             79 80 81 82
         
        
       
      

邻接表：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 #define MAXN 444 //邻接表要开边数的2倍 7  8 struct Edge{ 9     int v,cap,next;10 }edge[MAXN];11 int level[MAXN];//标记层次（距离标号）12 13 //间隙优化，定义gap[i]为标号是i的点的个数14 //在重标记i时，检查gap[level[i]],若减为0,这算法结束。15 int gap[MAXN];16 17 int pre[MAXN];//前驱18 int cur[MAXN];19 int head[MAXN];20 int NV,NE;21 22 //NE为边数，初始化为0；23 void Insert(int u,int v,int cap,int cc=0){24     edge[NE].cap=cap;edge[NE].v=v;25     edge[NE].next=head[u];head[u]=NE++;26 27     edge[NE].cap=cc;edge[NE].v=u;28     edge[NE].next=head[v];head[v]=NE++;29 }30 31 32 //参数，源点，汇点33 int SAP(int vs,int vt){34     memset(level,0,sizeof(level));35     memset(pre,-1,sizeof(pre));36     memset(gap,0,sizeof(gap));37     //cur[i]保存的是当前弧38     for(int i=0;i<=NV;i++)cur[i]=head[i];39     int u=pre[vs]=vs;//源点的pre还是其本身40     int maxflow=0,aug=-1;41     gap[0]=NV;42     while(level[vs]
          
           level[v]){71                 cur[u]=i;//保存弧72                 minlevel=level[v];73             }74         }75         if((--gap[level[u]])==0)break;//更新gap数组后如果出现断层，则直接退出。76         level[u]=minlevel+1;//重标号77         gap[level[u]]++;//距离标号为level[u]的点的个数+1;78         u=pre[u];//转当前点的前驱节点继续寻找可行弧79     }80     return maxflow;81 } 82 83 int main(){84     int m;//边的条数85     while(~scanf("%d%d",&m,&NV)){86         memset(head,-1,sizeof(head));87         NE=0;88         for(int i=1;i<=m;i++){89             int u,v,cap;90             scanf("%d%d%d",&u,&v,&cap);91             Insert(u,v,cap);92         }93         printf("%d\n",SAP(1,NV));94     }95     return 0;96 }