求递归实现sap算法(最短增广路)的pascal代码,要包括GAP优化. (最好有注释,让我这个菜鸟看得懂吧)

2025-02-06 09:10:26
推荐回答(3个)
回答1:

procedure sap;
begin
flow:=0;
for i:=1 to n do di[i]:=1;
num[0]:=n;
i:=1;
while dist[1] begin
flag:=false;
for k:=di[i] to top[i] do
begin
j:=a[i,k];
if (map[i,j]=true)and(dist[i]=dist[j]+1) then
begin
flag:=true;
pre[j]:=i;
di[i]:=k;
i:=j;
if i=n then
begin
flow:=flow+1;
while i<>1 do
begin
temp:=pre[i];
map[temp,i]:=false;
inc(top[i]);
a[i,top[i]]:=temp;
map[i,temp]:=true;
i:=pre[i];
end;
end;
break;
end;
end;
if flag=true then continue;
min:=n-1;
for k:=1 to top[i] do
begin
j:=a[i,k];
if (map[i,j]=true)and(dist[j] begin
min:=dist[j];
jl:=k;
end;
end;
dec(num[dist[i]]);
if num[dist[i]]=0 then break;
dist[i]:=min+1;
inc(num[dist[i]]);
di[i]:=jl;
if i<>1 then i:=pre[i];
end;
writeln(flow);
end;
这是主过程部分。。。

回答2:

买本算法导论自己看吧。。。

回答3:

static int DiGui(int num)
{
if(num==1 || num==2)
{
return 1;
}
else
{
return DiGUi(num-1)+DiGUi(num-2);
}
}