2014 11 13

今天接触了sap算法，感觉收获很多，写一些心得。

上网查sap，“设点i的标号为D[i]，那么如果将满足D[i]=D[j]+1的弧(i,j)叫做允许弧，且增广时只走允许弧，那么就可以达到“怎么走都是最短路”的效果”。其实就是dinic 分层次的思想，d【i】即为当前点到汇点的距离，d数组给所有点分层。（如果不清楚自行查找）

维护距离标号的方法：当找增广路过程中发现某点出发没有允许弧时，将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。这种维护距离标号的方法的正确性我就不证了。由于距离标号的存在，由于“怎么走都是最短路”，所以就可以采用DFS找增广路，用一个栈保存当前路径的弧即可。当某个点的距离标号被改变时，栈中指向它的那条弧肯定已经不是允许弧了，所以就让它出栈，并继续用栈顶的弧的端点增广。还有一种在常数上有所优化的写法是改变距离标号时把当前弧设为那条提供了最小标号的弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。

这里重点讲二个优化。

1 当前弧：di【i】 记录以第i个点为开头的当前边的另一节点。注意his数组 ，它记录了当前路径中的最小值，防止因为aug的变化覆盖以前的结果。

2 gap优化：vh【i】 记录距离为i的节点个数。如果vh【i】=0  ，s、t就不连通，退出。当把一个节点的距离由x改为y时，inc【y】dec【x】。

 下面给出程序：

var
flag:boolean;
jl,min,flow,aug,j,m,n,tmp,a,b,c,i:longint;
his,pre,dis,vh,di:array[0..1024] of longint;
map:array[1..1024,1..1024] of longint;
begin
readln(m,n);
for i:=1 to m do
begin
readln(a,b,c);
inc(map[a,b],c);
end;
vh[0]:=n;
for i:=1 to n do di[i]:=1;
i:=1;
aug:=maxlongint;
while dis[1]<n do
begin
his[i]:=aug;
flag:=false;
for j:=di[i] to n do
begin
if (map[i,j]>0)and(dis[j]+1=dis[i]) then
begin
flag:=true;
di[i]:=j;
if map[i,j]<aug then aug:=map[i,j];
pre[j]:=i;
i:=j;
if i=n then
begin
inc(flow,aug);
while i<>1 do
begin
tmp:=i;
i:=pre[i];
dec(map[i,tmp],aug);
inc(map[tmp,i],aug);
end;
aug:=maxlongint;
end;
break;
end;
end;
if flag then continue;
min:=n-1;
for j:=1 to n do
begin
if (map[i,j]>0)and(dis[j]<min) then begin jl:=j;min:=dis[j];end;
end;
di[i]:=jl;
dec(vh[dis[i]]);
if vh[dis[i]]=0 then break;
dis[i]:=min+1;
inc(vh[dis[i]]);
if i<>1 then begin i:=pre[i];aug:=his[i];end;
end;
write(flow);
end.

sap 算法心得