主题:[讨论]关于最大费用最大流 +分
这是《信息技术竞赛辅导》这本书中的一段源代码 名为[b]最大费用最大流[/b]
program work;
const maxn=100;
type node1=record
w,f,c:integer
end;
type node2=record
value:integer;
fa:integer;
end;
var a:array[1..maxn+2,1..maxn+2] of node1;
best:array[1..maxn+2] of node2;
n,maxwork,s,t:integer;
procedure init;
var i,j:integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
for j:=n+1 to 2*n do
begin
read(a[i,j].w); *************
a[i,j].c:=1; *************
a[j,i].w:=-a[i,j].w; *************
end;
s:=2*n+1;
t:=2*n+2;
for i:=1 to n do
begin
a[s,i].c:=1;
a[n+i,t].c:=1;
end;
maxwork:=0;
end;
function find:boolean;
var i,j:integer;
quit:boolean;
begin
fillchar(best,sizeof(best),0);
best[s].value:=1;
repeat
quit:=true;
for i:=1 to 2*n+2 do
if best[i].value>0 then
for j:=1 to 2*n+2 do
if (a[i,j].f<a[i,j].c) then
if best[i].value+a[i,j].w>best[j].value then *********
begin
best[j].value:=best[i].value+a[i,j].w;
best[j].fa:=i;
quit:=false;
end;
until quit;
if best[t].value>1 then find:=true else find:=false;
end;
procedure add;
var i,j:integer;
begin
i:=t;
while i<>s do
begin
j:=best[i].fa;
inc(a[j,i].f);
a[i,j].f:=-a[j,i].f;
i:=j
end;
inc(maxwork,best[t].value-1);
end;
begin
init;
while find do add;
writeln(maxwork);
end.
其中加*的部分是我觉得有问题的部分 我用这段程序解了一道标准的最大费用最大流问题 结果很多不对 但如果把费用赋为负值 用标准[b]最小费用最大流[/b]去算就对了 也就是说这本书上提供的解同一题的两种方法是矛盾的 我认为是加*部分代码的问题
谁能告诉我求最大路径(无回复)用迭代Ford算法有没有理论根据 若有 为什么程序结果不对 是代码的问题么?
谢
program work;
const maxn=100;
type node1=record
w,f,c:integer
end;
type node2=record
value:integer;
fa:integer;
end;
var a:array[1..maxn+2,1..maxn+2] of node1;
best:array[1..maxn+2] of node2;
n,maxwork,s,t:integer;
procedure init;
var i,j:integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
for j:=n+1 to 2*n do
begin
read(a[i,j].w); *************
a[i,j].c:=1; *************
a[j,i].w:=-a[i,j].w; *************
end;
s:=2*n+1;
t:=2*n+2;
for i:=1 to n do
begin
a[s,i].c:=1;
a[n+i,t].c:=1;
end;
maxwork:=0;
end;
function find:boolean;
var i,j:integer;
quit:boolean;
begin
fillchar(best,sizeof(best),0);
best[s].value:=1;
repeat
quit:=true;
for i:=1 to 2*n+2 do
if best[i].value>0 then
for j:=1 to 2*n+2 do
if (a[i,j].f<a[i,j].c) then
if best[i].value+a[i,j].w>best[j].value then *********
begin
best[j].value:=best[i].value+a[i,j].w;
best[j].fa:=i;
quit:=false;
end;
until quit;
if best[t].value>1 then find:=true else find:=false;
end;
procedure add;
var i,j:integer;
begin
i:=t;
while i<>s do
begin
j:=best[i].fa;
inc(a[j,i].f);
a[i,j].f:=-a[j,i].f;
i:=j
end;
inc(maxwork,best[t].value-1);
end;
begin
init;
while find do add;
writeln(maxwork);
end.
其中加*的部分是我觉得有问题的部分 我用这段程序解了一道标准的最大费用最大流问题 结果很多不对 但如果把费用赋为负值 用标准[b]最小费用最大流[/b]去算就对了 也就是说这本书上提供的解同一题的两种方法是矛盾的 我认为是加*部分代码的问题
谁能告诉我求最大路径(无回复)用迭代Ford算法有没有理论根据 若有 为什么程序结果不对 是代码的问题么?
谢