Program Max_Flow_Min_Cost; //注意:图中任意两点之间至多有一条直连通有向边!!type
nettype=record
c, w ,f:longint; //弧的容量,每单位通过量费用,可行流量
end;
btype=record
v,fa:longint; //到源点的最短距离,父辈
end;
var net:array[1..100,1..100]of nettype; //网络N的邻接矩阵
best:array[1..100]of btype; //求最短路时用的数组
n,s,t:longint; //顶点数,源点、汇点的编号
minc:longint; //最小总费用
procedure init; //边目录输入
var a,b:word;c,d:longint;
begin
minc:=0;
fillchar(net,sizeof(net),0);
assign(input,'flow.in');reset(input);
assign(output,'flow.out');rewrite(output);
read(n,s,t); //注意: 这里s<>t!! **允许s到t无路(输出0)**
read(a,b,c,d);
while a+b+c+d>0 do
begin
net[a,b].c:=c;{给弧(a,b)赋容量c}//这里两点只有一条有向边!!-**问题关键**-
net[a,b].w:=d;{给弧(a,b)赋费用d}
net[b,a].w:=-d;{给相反孤(b,a)赋费用-d}
readln(a,b,c,d);
end;
end;
procedure print; {输出最小费用最大流的费用及方案}
var i,j:word;
begin
writeln('MinCost=',minc);
for i:=1 to n do
for j:=1 to n do
if net[i,j].f>0 then
writeln(i,'-->',j,' : ',net[i,j].w,'*',net[i,j].f);
close(input);
close(output);
end;
function Find_Way:boolean; {求最小费用增广路函数,若best[t].value<>MaxInt,则找到增广路,函数返回true,否则返回false}
var i,j:word;
quit:boolean;
begin
for i:=1 to n do best[i].v:=maxlongint; //寻求最小费用增广路径前,给best数组赋初值
best[s].v:=0;
repeat
quit:=true;
for i:=1 to n do
if best[i].v<maxlongint then
for j:=1 to n do
if (net[i,j].f<net[i,j].c)and(best[i].v+net[i,j].w<best[j].v) then
begin
best[j].v:=best[i].v+net[i,j].w;
best[j].fa:=i;
quit:=false;
end;
until quit;
if best[t].v<maxlongint then Find_Way:=true
else Find_Way:=false;
end;
procedure Add_Way;
var i,j:word;
begin
i:=t;
repeat
j:=i;i:=best[j].fa;
inc(net[i,j].f); //增广路是弧的数量修改,增量1
net[j,i].f:=-net[i,j].f; //给对应相反弧的流量赋值-f
until i=s;
inc(minc,best[t].v); //修改最小总费用的值
end;
begin
init;
while Find_Way do Add_Way; //当找到最小费用增广路,修改流
print;
end.
最小费最大流。题目打错了。