type alice=record
x,y,f,c,next,op:longint;
end;
var tot,n,a,b,c,d,cost,x,i,k,del,now,head,tail,s,t:longint;
bian:array[-10..10000]of alice;
first,q,w,pre:array[-10..10000]of longint;
v:array[-10..10000]of boolean;
procedure connect(a,b,c,d:longint);
begin
inc(tot);
bian[tot].x:=a;
bian[tot].y:=b;
bian[tot].f:=c;
bian[tot].c:=d;
bian[tot].op:=tot+1;
bian[tot].next:=first[a];
first[a]:=tot;
inc(tot);
bian[tot].x:=b;
bian[tot].y:=a;
bian[tot].f:=0;
bian[tot].c:=-d;
bian[tot].op:=tot-1;
bian[tot].next:=first[b];
first[b]:=tot;
end;
procedure main;
begin
while 1=1 do
begin
for i:=1 to n do w[i]:=maxlongint;
head:=0; tail:=1;
q[1]:=s; v[s]:=true; w[s]:=0;
repeat
inc(head);
x:=q[head];
k:=first[x];
while k<>0 do with bian[k] do
begin
if f>0 then
if w[y]>w[x]+c then
begin
w[y]:=w[x]+c;
pre[y]:=k;
if not v[y] then
begin
inc(tail);
q[tail]:=y;
v[y]:=true;
end;
end;
k:=next;
end;
v[x]:=false;
until head=tail;
if w[t]=maxlongint then break;
now:=t; del:=maxlongint;
while now<>s do with bian[pre[now]] do
begin
if f<del then del:=f;
now:=x;
end;
now:=t;
while now<>s do with bian[pre[now]] do
begin
dec(f);
inc(bian[op].f);
now:=x;
end;
inc(cost,del*w[t]);
end;
writeln(cost);
end;
begin
assign(input,'ex.in');
assign(output,'ex.out');
reset(input);
rewrite(output);
fillchar(v,sizeof(false),false);
cost:=0;
readln(n);
s:=1;t:=n;
readln(a,b,c,d);
while (a<>0)and(b<>0) do
begin
connect(a,b,c,d);
readln(a,b,c,d);
end;
main;
close(input);
close(output);
end.
用spfa求最小费用最大流,不过?