关于最小费用最大流

来源：百度知道 编辑：UC知道 时间：2024/07/07 19:58:23
program exe1;
const maxm=10000;maxn=1000;
type path=record
st,ed,c,f,di,nt:longint;
end;
var dis,start,t,st:array[1..maxn]of longint;
pt:array[1..maxm]of path;
i,j,k,l,m,n,flow,cost,delta:longint;
function min(a,b:longint):longint;
begin
if a<b then min:=a
else min:=b;
end;
function connect:boolean;
var i,j,k,op,cl:longint;
d:array[1..10000]of longint;
t:array[1..maxn]of longint;
begin
dis[1]:=0;
for i:=2 to maxn do dis[i]:=maxlongint;
fillchar(t,sizeof(t),0);t[1]:=1;fillchar(d,sizeof(d),0);
op:=1;cl:=2;d[1]:=1;
while op<cl do
begin
j:=d[op];k:=start[j];
while k<>0 do
begin
if (odd(k) and (pt[k].f<pt[k].c) and (dis[j]+pt[k].di<dis[pt[k].ed]))
or((not(odd(k))) and (pt[k-1].f>0) and (dis[j]+pt[k].di<dis[pt[k].ed])) then
beg

const
maxn=100;
maxq=100000;

var
p,c,f:array[1..maxn,1..maxn] of longint;
dist,path:array[1..maxn] of longint;
q:array[1..maxq] of longint;
check:array[1..maxn] of 0..1;
n,m:longint;
mark:boolean;

procedure init;
var
s,t,r,w,i,j:longint;
begin
readln (n);
readln (m);
for i:=1 to m do begin
readln (s,t,r,w);
c[s,t]:=r;p[s,t]:=w;
end;
end;

procedure main;
var
i,j,a,r,l,k:longint;
begin
fillchar(f,sizeof(f),0);
mark:=true;
while mark do begin
q[1]:=1;r:=0;l:=1;
mark:=false;
for i:=2 to n do dist[i]:=maxlongint;
fillchar(check,sizeof(check),0);dist[1]:=0;
fillchar(path,sizeof(path),0);
while r<l do begin