1834: [ZJOI2010]network 网络扩容 (最小费用最大流模板）

const inf=10000000;
var
  other,a,dis,pre,uu,vv,ww,next,head,e,x,long,w:array[0..50100]of longint;
  v:Array[0..10010]of boolean;
  tt,c,ee,s,t,i,j,ans,mincost,n,m,k:longint;
function min(aa,bb:longint):longint;
  begin
  if aa>bb then exit(bb)
  else exit(aa);
  end;
 
function spfa:boolean;
  var i,h,t,j:longint;
  begin
  h:=1;t:=1;
  for i:=0 to tt do dis[i]:=inf;
  a[1]:=s; pre[s]:=-1;
  v[1]:=true;  dis[s]:=0;
  while h<=t do
    begin
    j:=head[a[h]];
    while j<>0 do
      begin
      if (long[j]>0)and(dis[a[h]]+w[j]<dis[e[j]]) then
        begin
        dis[e[j]]:=dis[a[h]]+w[j];
        pre[e[j]]:=j;
        if not v[e[j]] then
          begin
          v[e[j]]:=true;
          inc(t);a[t]:=e[j];
          end;
        end;
      j:=next[j];
      end;
    v[a[h]]:=false;
    inc(h);
    end;
  if dis[tt]>=inf-1000 then exit(false)
  else exit(true);
  end;
 
procedure work;
  var zh,flow:longint;
  begin
  ans:=0;
  mincost:=0;
  while spfa do
    begin
    zh:=tt;
    flow:=maxlongint;
    while pre[zh]<>-1 do
      begin
      flow:=min(flow,long[pre[zh]]);
      zh:=x[pre[zh]];
      end;
    ans:=ans+flow;
    mincost:=mincost+dis[tt]*flow;
    zh:=tt;
    while pre[zh]<>-1 do
      begin
      dec(long[pre[zh]],flow);
      inc(long[other[pre[zh]]],flow);
      zh:=x[pre[zh]];
      end;
    end;
  end;
 
procedure add(u,v,c,cc:longint);
  begin
  inc(ee);x[ee]:=u;e[ee]:=v;long[ee]:=c;w[ee]:=cc;other[ee]:=ee+1;
  next[ee]:=head[u];head[u]:=ee;
  inc(ee);x[ee]:=v;e[ee]:=u;long[ee]:=0;w[ee]:=-cc;other[ee]:=ee-1;
  next[ee]:=head[v];head[v]:=ee;
  end;
 
begin
  readln(n,m,k);
  for i:=1 to m do
    begin
    readln(uu[i],vv[i],c,ww[i]);
    add(uu[i],vv[i],c,0);
    end;
  s:=1;tt:=n;
  work;
  write(ans,' ');
  tt:=n+1;
  add(n,n+1,k,0);
  for i:=1 to m do
    add(uu[i],vv[i],inf,ww[i]);
  work;
  writeln(mincost);
  end.