bzoj 1834最大ストリーム+最小費用最大ストリーム

テンプレートになりますが...この問題の2番目の質問の構図はやはり考えてみてください...残量ネットワークでは元のエッジをすべて加算しますが、費用wがあり、容量は無限大で、最初のエッジはやはり費用0でソースポイントsを新規作成し、sは1連1辺、容量はk、費用は0で、このエッジが満流であることを保証し、最小の費用があります.

program bzoj1834;
type point=record
        s,t,cap,flow,o,w,next:longint;
end;
var p,l,n,m,k,c,i:longint;
      v1:array[0..1010]of boolean;
      edge:array[1..30010]of point;
      head,d:array[0..1010]of longint;
      b:array[1..10000000]of longint;
      u,v,w:array[0..5010]of longint;
procedure add(u,v,c,w:longint);
begin
 l:=l+1;
 edge[l].s:=u;
 edge[l].t:=v;
 edge[l].cap:=c;
 edge[l].flow:=0;
 edge[l].o:=l+1;
 edge[l].w:=w;//  
 edge[l].next:=head[u];
 head[u]:=l;
 l:=l+1;
 edge[l].s:=v;
 edge[l].t:=u;
 edge[l].cap:=c;
 edge[l].flow:=c;
 edge[l].o:=l-1;
 edge[l].w:=-w;
 edge[l].next:=head[v];
 head[v]:=l;
end;
function min(a,b:longint):longint;
begin
 if a<b then min:=a else min:=b;
end;

function bfs:boolean;
var top,tail,p:longint;
begin
 d[1]:=1;
 top:=1;tail:=1;
 b[1]:=1;
 fillchar(v1,sizeof(v1),false);
 v1[1]:=true;
 repeat
  p:=head[b[top]];
  while p<>-1 do
       begin
         if (v1[edge[p].t]=false)and(edge[p].cap>edge[p].flow) then
              begin
               v1[edge[p].t]:=true;
               d[edge[p].t]:=d[b[top]]+1;//  
               tail:=tail+1;
               b[tail]:=edge[p].t;
              end;
         p:=edge[p].next;
       end;
  top:=top+1;
 until top>tail;
 exit(v1[n]);
end;



function addflow(x,maxflow:longint):longint;
var p,o:longint;
begin
  if (x=n) or (maxflow=0) then exit(maxflow);
  addflow:=0;//      ！！
  p:=head[x];
  while p<>-1 do
       begin
         if (d[edge[p].t]=d[x]+1)and(edge[p].cap>edge[p].flow) then
          begin
            o:=addflow(edge[p].t,min(maxflow,edge[p].cap-edge[p].flow));
            if o>0 then
             begin
               inc(edge[p].flow,o);
               dec(edge[edge[p].o].flow,o);
               maxflow:=maxflow-o;
               addflow:=addflow+o;
               if maxflow=0 then break;
             end;
          end;
         p:=edge[p].next;
       end;
end;



function dinic:longint;
begin
 dinic:=0;
 while bfs do
      dinic:=dinic+addflow(1,maxlongint);
end;

function spfa:longint;
var cost,top,tail,i,p:longint;
      pre,re:array[0..1010]of longint;
      flag:array[0..1010]of boolean;
      d:array[0..1010]of longint;
      mm:longint;
begin
 cost:=0;
 while true do
    begin
      top:=1;tail:=1;
      b[1]:=0;
      for i:=0 to n do d[i]:=maxlongint;
      d[0]:=0;//  
      fillchar(pre,sizeof(pre),0);
      pre[0]:=-1;
      fillchar(re,sizeof(re),0);
      fillchar(flag,sizeof(flag),true);
      flag[0]:=false;
      repeat
       p:=head[b[top]];
       while p<>-1 do
         begin
          if (edge[p].cap>edge[p].flow)and(d[b[top]]+edge[p].w<d[edge[p].t]) then
            begin
             d[edge[p].t]:=d[b[top]]+edge[p].w;
             pre[edge[p].t]:=b[top];
             re[edge[p].t]:=p;
             if flag[edge[p].t] then
              begin
                flag[edge[p].t]:=false;
                tail:=tail+1;
                b[tail]:=edge[p].t;
              end;
            end;
          p:=edge[p].next;
         end;
        flag[b[top]]:=true;
        top:=top+1;
      until top>tail;
      if d[n]=maxlongint then break;
      i:=n;
      mm:=maxlongint;
      while pre[i]<>-1 do
        begin
          mm:=min(mm,edge[re[i]].cap-edge[re[i]].flow);
          i:=pre[i];
        end;
      i:=n;
      while pre[i]<>-1 do
        begin
         inc(edge[re[i]].flow,mm);
         dec(edge[edge[re[i]].o].flow,mm);
         cost:=cost+mm*edge[re[i]].w;
         i:=pre[i];
        end;
    end;
  spfa:=cost;
end;
begin
 read(n,m,k);
 for i:=0 to n do head[i]:=-1;
 for i:=1 to m do
     begin
       read(u[i],v[i],c,w[i]);
       add(u[i],v[i],c,0);
     end;
 write(dinic,' ');
 //       
 for i:=1 to m do
    add(u[i],v[i],maxlongint,w[i]);
 add(0,1,k,0);

 writeln(spfa);
 readln;readln;
end.