网络流最大流之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贴上模版：
http://acm.hdu.edu.cn/showproblem.php?pid=1532 （hdu1532 problem链接）
邻接矩阵：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
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]<vt){
21 //寻找可行弧
22 for(v=1;v<=vt;v++){
23 if(map[u][v]>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 }
邻接表：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 #define MAXN 444 //邻接表要开边数的2倍
7
8 struct Edge{
9 intv,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]<NV){
43 loop :
44 for(int &i=cur[u];i!=-1;i=edge[i].next){
45 int v=edge[i].v;//v是u的后继
46 //寻找可行弧
47 if(edge[i].cap&&level[u]==level[v]+1){
48 //aug表示增广路的可改进量
49 aug==-1?(aug=edge[i].cap):(aug=min(aug,edge[i].cap));
50 pre[v]=u;
51 u=v;
52 //如果找到一条增广路
53 if(v==vt){
54 maxflow+=aug;//更新最大流；
55 //路径回溯更新残留网络
56 for(u=pre[v];v!=vs;v=u,u=pre[u]){
57 //前向弧容量减少，反向弧容量增加
58 edge[cur[u]].cap-=aug;
59 edge[cur[u]^1].cap+=aug;
60 }
61 aug=-1;
62 }
63 goto loop;
64 }
65 }
66 int minlevel=NV;
67 //寻找与当前点相连接的点中最小的距离标号（重标号）
68 for(int i=head[u];i!=-1;i=edge[i].next){
69 int v=edge[i].v;
70 if(edge[i].cap&&minlevel>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 }