网络流sap算法
对于学习了dinic算法之后,再来看sap算法,其实就没什么难的了,dinic是多次bfs然后dfs找增广路,sap是一次bfs然后多次重标号.当然sap还可以用gap优化.也就是如果断层了的话,那么就可以直接退出了.具体的是先进行一次bfs构建层次图和初始化gap数组,然后当dist[source]<N的时候(source表示源点,N表示顶点的个数dist是层次图的信息)一直循环,如果找到一条增广路径的话,就改变残留网络和最大流,如果当前点的出度为0(包括层次图的信息)那么就退栈,并且改变层次图的信息和gap数组,改变gap数组之后如果发现已经断层了,那么就直接退出了,下面给出USACO4.2.1的sap版代码:
/
ID:qcx97811
LANG:C
TASK:ditch
/
#include
#include
#include
#include
int graph[206][206],d[206],gap[206];
int N,M,maxflow
void bfs()
{
int i,j
int q[206];
int front,rear
front = -1
q[rear=0]=M
memset(d,-1,sizeof(d));
d[M]=0
memset(gap,0,sizeof(gap));
gap[0]=1
while(front < rear)
{
i = q[++front];
for(j = 1j <= M;j++)
{
if(-1 == d[j] & graph[j][i] > 0)
{
d[j] = d[i]+1
q[++rear] = j
gap[d[j]]++
}
}
}
}
void sap()
{
int i,j
int top,q[206],low[206];
bfs();
#if 0
printf(“%d %d %d %d\n”,d[1],d[2],d[3],d[4]);
printf(“——–after bfs\n”);
#endif
top=0
low[0]=INT_MAX
q[top]=1
while(d[1] < M)
{
for(i = 1i <= M;i++)
{
if(graph[q[top]][i] > 0 & d[i]+1==d[q[top]])
{
q[++top]=i
low[top]=graph[q[top-1]][i];
if(low[top] > low[top-1])//到当前点的增广流的最大值
low[top]=low[top-1];
break
}
}
if(i != (M+1))//注意这里是M+1和上面的for循环的出口对应 应该是for循环的最大值+1
{
if(M == q[top])//如果已经找到一条增广路
{
for(i = 0i < top;i++)
{//更新残留网络
graph[q[i]][q[i+1]] -= low[top];
graph[q[i+1]][q[i]] += low[top];
}
maxflow += low[top];//更改结果
top = 0//重新从源点开始找
}
}
else
{
j = q[top];
gap[d[j]]–//这个点对应的层次的点的个数-1
if(gap[d[j]] == 0)//如果-1之后==0那么就出现了断层,可以直接退出了,至于证明这个应该不难吧.
{
break
}
d[j] = M+1
for(i = 1i <= M;i++)
{
if(graph[j][i] > 0 & d[i]+1 < d[j] && d[i] >= 0)
{//注意这里的d[i] >= 0因为并不是所有的点都在层次图中
d[j]=d[i]+1
}
}
gap[d[j]]++//对应的点的层次的点的个数+1
if(top>0)//如果不是源点就退到前一个顶点
top–
}
}
return ;
}
int main(void)
{
freopen(“ditch.in”,“r”,stdin);
freopen(“ditch.out”,“w”,stdout);
int i,s,e,c
scanf(“%d%d”,N,&M);
memset(graph,0,sizeof(graph));
for(i = 0i < N;i++)
{
scanf(“%d%d%d”,s,&e,&c);
graph[s][e] += c
}
sap();
printf(“%d\n“,maxflow);
return 0
}
ID:qcx97811
LANG:C
TASK:ditch
/
#include
#include
#include
#include
int graph[206][206],d[206],gap[206];
int N,M,maxflow
void bfs()
{
int i,j
int q[206];
int front,rear
front = -1
q[rear=0]=M
memset(d,-1,sizeof(d));
d[M]=0
memset(gap,0,sizeof(gap));
gap[0]=1
while(front < rear)
{
i = q[++front];
for(j = 1j <= M;j++)
{
if(-1 == d[j] & graph[j][i] > 0)
{
d[j] = d[i]+1
q[++rear] = j
gap[d[j]]++
}
}
}
}
void sap()
{
int i,j
int top,q[206],low[206];
bfs();
#if 0
printf(“%d %d %d %d\n”,d[1],d[2],d[3],d[4]);
printf(“——–after bfs\n”);
#endif
top=0
low[0]=INT_MAX
q[top]=1
while(d[1] < M)
{
for(i = 1i <= M;i++)
{
if(graph[q[top]][i] > 0 & d[i]+1==d[q[top]])
{
q[++top]=i
low[top]=graph[q[top-1]][i];
if(low[top] > low[top-1])//到当前点的增广流的最大值
low[top]=low[top-1];
break
}
}
if(i != (M+1))//注意这里是M+1和上面的for循环的出口对应 应该是for循环的最大值+1
{
if(M == q[top])//如果已经找到一条增广路
{
for(i = 0i < top;i++)
{//更新残留网络
graph[q[i]][q[i+1]] -= low[top];
graph[q[i+1]][q[i]] += low[top];
}
maxflow += low[top];//更改结果
top = 0//重新从源点开始找
}
}
else
{
j = q[top];
gap[d[j]]–//这个点对应的层次的点的个数-1
if(gap[d[j]] == 0)//如果-1之后==0那么就出现了断层,可以直接退出了,至于证明这个应该不难吧.
{
break
}
d[j] = M+1
for(i = 1i <= M;i++)
{
if(graph[j][i] > 0 & d[i]+1 < d[j] && d[i] >= 0)
{//注意这里的d[i] >= 0因为并不是所有的点都在层次图中
d[j]=d[i]+1
}
}
gap[d[j]]++//对应的点的层次的点的个数+1
if(top>0)//如果不是源点就退到前一个顶点
top–
}
}
return ;
}
int main(void)
{
freopen(“ditch.in”,“r”,stdin);
freopen(“ditch.out”,“w”,stdout);
int i,s,e,c
scanf(“%d%d”,N,&M);
memset(graph,0,sizeof(graph));
for(i = 0i < N;i++)
{
scanf(“%d%d%d”,s,&e,&c);
graph[s][e] += c
}
sap();
printf(“%d\n“,maxflow);
return 0
}
