最大流SAP算法的当前弧优化
找了很多资料和程序，大多是编程风格和语言实在和我的不相符和。终于搞得有点明白了。因为找的时候会有很多不可行的弧，在距离标号修改之前还是不可行的，那么我们引入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 of longint;
h,vh,cur:Array 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>0 then
begin
if h=h-1 then
begin
if c>now then
tmp:=aug(j,now)
else tmp:=aug(j,c);
dec(c,tmp);
inc(c,tmp);
dec(now,tmp);
inc(aug,tmp);
if h>=n then exit;
if now=0 then break;
end;
end;
if aug=0 then
begin
for j:=1 to n do
if (c>0) and (h<minh) then
begin
minh:=h;
k:=j;
end;
cur:=k;//cur优化
dec(vh]);
if vh]<=0 then h:=n;
h:=minh+1;
inc(vh]);
end;
end;
procedure sap;
begin
fillchar(vh,sizeof(vh),0);
fillchar(h,sizeof(h),0);
vh:=n;
for i:=1 to n do
cur:=1;//初始化当前弧
while h<n do
aug(1,oo);
end;
begin
readln(m,n);
for i:=1 to m do
begin
readln(x,y,z);
c:=z;
end;
sap;
writeln(maxflow);
end.
页:
[1]