最大流SAP算法的当前弧优化

lishenghan

　　找了很多资料和程序，大多是编程风格和语言实在和我的不相符和。终于搞得有点明白了。因为找的时候会有很多不可行的弧，在距离标号修改之前还是不可行的，那么我们引入cur数组，标志可行的第一条弧，每次如果修改了距离标号的话就修改它。据这位说："早就听说当前弧优化，但是一加到自己代码上就错。这次终于找到原因了，因为以前把更新距离标号的一部分操作挪到寻找可行弧时完成，但这样一来就会出现问题。把操作独立出来之后问题就解决了。"并且另外一位大牛的程序似乎也是这样的。于是懒惰的我就没有继续思考了，就把这个思路整合到自己的代码里，提交了一道裸的最大流，AC了，程序应该没问题吧。
　　参考：

　　http://baike.dangzhi.com/wiki/SAP#SAP.E7.AE.97.E6.B3.95
　　http://hi.baidu.com/lemon_workshop/blog/item/ab28ecbc71717d0718d81f15.html
　　http://dementrock.ixiezi.com/2010/07/28/noi-2006-%E6%9C%80%E5%A4%A7%E8%8E%B7%E5%88%A9/
　　
　　

　　我想应该很少有题目能卡SAP+GAP+CUR的程序了吧……
　　附：我的RQNOJ194程序
const
oo=19930508;
var
c:array[0..1000,0..1000] of longint;
h,vh,cur:Array[0..1000] of longint;
maxflow,n,m,i,j,k,x,y,z:longint;

function aug(i,now:longint):longint;
var
k,minh,tmp,j:longint;
begin
aug:=0;
minh:=n-1;
if i=n then
begin
inc(maxflow,now);
exit(now);
end;
for j:=1 to n do
if c[i,j]>0 then
begin
if h[j]=h-1 then
begin
if c[i,j]>now then
tmp:=aug(j,now)
else tmp:=aug(j,c[i,j]);
dec(c[i,j],tmp);
inc(c[j,i],tmp);
dec(now,tmp);
inc(aug,tmp);
if h[1]>=n then exit;
if now=0 then break;
end;
end;
if aug=0 then
begin
for j:=1 to n do
if (c[i,j]>0) and (h[j]<minh) then
begin
minh:=h[j];
k:=j;
end;
cur:=k;//cur优化
dec(vh[h]);
if vh[h]<=0 then h[1]:=n;
h:=minh+1;
inc(vh[h]);
end;
end;
procedure sap;
begin
fillchar(vh,sizeof(vh),0);
fillchar(h,sizeof(h),0);
vh[0]:=n;
for i:=1 to n do
cur:=1;//初始化当前弧
while h[1]<n do
aug(1,oo);
end;
begin
readln(m,n);
for i:=1 to m do
begin
readln(x,y,z);
c[x,y]:=z;
end;
sap;
writeln(maxflow);
end.