使用Dijkstra优化费用流

{$INLINE ON}
program Dijkstra_Optimised_Costflow;

type tnode=record
        n,c,w,next:longint;
     end;

const maxn=100017;
      maxm=1000017;
      maxint=longint($3f3f3f3f);

var g,h,d,q,pre,arc,dlt:array[0..maxn] of longint;
    t:array[0..maxn*4] of longint;
    v:array[0..maxn] of boolean;
    mem:array[0..maxm] of tnode;
    n,m,memsize,st,trm,flow,cost,zkw,frt,rer:longint;

function min(i,j:longint):longint; inline; begin if i<j then exit(i) else exit(j); end;

procedure insnbs(u,v,ic,iw:longint); inline;
begin
inc(memsize); with mem[memsize] do begin
        n:=v; c:=ic; w:=iw; next:=g[u];
end; g[u]:=memsize;
inc(memsize); with mem[memsize] do begin
        n:=u; c:=0; w:=-iw; next:=g[v];
end; g[v]:=memsize;
end;

procedure spfa;
var head,tail,t1:longint;
begin
fillchar(h,sizeof(h),$3f); h[st]:=0; frt:=0; rer:=1; q[1]:=st; v[st]:=true;
while frt<>rer do begin frt:=frt mod maxn+1; head:=q[frt];
        t1:=g[head]; while t1<>0 do begin tail:=mem[t1].n;
                if (mem[t1].c>0)and(h[tail]>h[head]+mem[t1].w) then begin
                        h[tail]:=h[head]+mem[t1].w; if not v[tail] then begin
                                rer:=rer mod maxn+1; q[rer]:=tail; v[tail]:=true;
                        end;
                end; t1:=mem[t1].next;
        end; v[head]:=false;
end;
end;

procedure edit(i,j:longint); inline;                                                    begin
inc(i,zkw); t[i]:=j; while i>1 do begin j:=i>>1; t[j]:=min(t[i],t[i xor 1]); i:=j; end; end;

procedure ek_dijkstra;
var i,j,k,u,w,t1:longint;
begin
zkw:=1; while zkw<n+2 do zkw:=zkw<<1; d[trm]:=0; flow:=0; cost:=0; while d[trm]<maxint do begin
        d[trm]:=maxint; fillchar(t,(zkw+1)<<3,$3f); fillchar(v,sizeof(v),0);
        edit(st,0); dlt[st]:=maxint; pre[st]:=0; for i:=1 to n do begin
                j:=1; while j<zkw do begin k:=j<<1; j:=k+byte(t[k xor 1]<t[k]); end;
                if t[j]=maxint then break; dec(j,zkw); d[j]:=t[j+zkw]; v[j]:=true; edit(j,maxint);
                t1:=g[j]; while t1<>0 do begin k:=mem[t1].n; w:=mem[t1].w+h[j]-h[k];
                        if (mem[t1].c>0)and(not v[k])and(t[k+zkw]>d[j]+w) then begin
                                pre[k]:=j; arc[k]:=t1; dlt[k]:=min(dlt[j],mem[t1].c); edit(k,d[j]+w);
                        end; t1:=mem[t1].next;
                end;
        end; if d[trm]-h[st]+h[trm]<maxint then begin
                u:=trm; w:=dlt[trm]; inc(flow,w); inc(cost,(d[trm]-h[st]+h[trm])*w);
                while u<>st do begin dec(mem[arc[u]].c,w); inc(mem[arc[u]xor 1].c,w); u:=pre[u]; end;
                for i:=1 to n do inc(h[i],d[i]);
        end else break;
end;
end;

procedure init;
var i,j,k,u,v,c,w:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,m); for i:=1 to m do begin
        readln(u,v,c,w); insnbs(u,v,c,w);
end; st:=1; trm:=n;
end;

begin
init;
ek_dijkstra;
writeln(flow,' ',cost);
end.