网络流之SAP算法学习

有你才完美WoW

　　终于决定开始学习网络流了=.=
　　<<图论算法理论、实践与应用>>那本书讲了很多关于求最大流的算法，然后我就只挑了一种传说中神奇的SAP算法学习。
　　首先引入几个新名词：
　　1、距离标号：
　　所谓距离标号 ，就是某个点到汇点的最少的弧的数量（即边权值为1时某个点到汇点的最短路径长度）。

　　设点i的标号为level，那么如果将满足level=level[j]+1的弧(i,j)叫做允许弧 ，且增广时只走允许弧。
　　2、断层（本算法的Gap优化思想）：
　　gap数组表示距离标号为i的点有多少个，如果到某一点没有符合距离标号的允许弧，那么需要修改距离标号来找到增广路；
　　如果重标号使得gap数组中原标号数目变为0，则算法结束。
　　SAP算法框架：
　　1、初始化；
　　2、不断沿着可行弧找增广路。可行弧的定义为{( i , j ) , level==level[j]+1};
　　3、当前节点遍历完以后，为了保证下次再来的时候有路可走，重新标号当前距离，level=min(level[j]+1);
　　该算法最重要的就是gap常数优化了。
　　下面对hdu 1532贴上模版：
　　http://acm.hdu.edu.cn/showproblem.php?pid=1532
　　邻接矩阵：


View Code


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[v]>0&&level==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){
34                     if(aug>map[pre])aug=map[pre];
35                 }
36                 maxflow+=aug;
37                 //更新残留网络
38                 for(int i=v;i!=vs;i=pre){
39                     map[pre]-=aug;
40                     map[pre]+=aug;
41                 }
42                 u=vs;//从源点开始继续搜
43             }
44         }else {
45             //找不到可行弧
46             int minlevel=vt;
47             //寻找与当前点相连接的点中最小的距离标号
48             for(v=1;v<=vt;v++){
49                 if(map[v]>0&&minlevel>level[v]){
50                     minlevel=level[v];
51                 }
52             }
53             gap[level]--;//(更新gap数组）当前标号的数目减1；
54             if(gap[level]==0)break;//出现断层
55             level=minlevel+1;
56             gap[level]++;
57             u=pre;
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[v]+=cap;
70         }
71         printf("%d\n",SAP(1,n));
72     }
73     return 0;
74 }
75
76
77            
78            
79
80
81
82                 
　　邻接表：


View Code


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     int v,cap,next;
10 }edge[MAXN];
11 int level[MAXN];//标记层次（距离标号）
12
13 //间隙优化，定义gap为标号是i的点的个数
14 //在重标记i时，检查gap[level],若减为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;head=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保存的是当前弧
38     for(int i=0;i<=NV;i++)cur=head;
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;i!=-1;i=edge.next){
45             int v=edge.v;//v是u的后继
46             //寻找可行弧
47             if(edge.cap&&level==level[v]+1){
48                 //aug表示增广路的可改进量
49                 aug==-1?(aug=edge.cap):(aug=min(aug,edge.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){
57                         //前向弧容量减少，反向弧容量增加
58                         edge[cur].cap-=aug;
59                         edge[cur^1].cap+=aug;
60                     }
61                     aug=-1;
62                 }
63                 goto loop;
64             }
65         }
66         int minlevel=NV;
67         //寻找与当前点相连接的点中最小的距离标号（重标号）
68         for(int i=head;i!=-1;i=edge.next){
69             int v=edge.v;
70             if(edge.cap&&minlevel>level[v]){
71                 cur=i;//保存弧
72                 minlevel=level[v];
73             }
74         }
75         if((--gap[level])==0)break;//更新gap数组后如果出现断层，则直接退出。
76         level=minlevel+1;//重标号
77         gap[level]++;//距离标号为level的点的个数+1;
78         u=pre;//转当前点的前驱节点继续寻找可行弧
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 }