首先先跑裸的最大流，然后加边，在残余网络上跑费用流

比较水

1 const max=1000000007;  2 type node=record  3        from,flow,cost,point,next:longint;  4      end;  5   6 var edge:array[0..100010] of node;  7     w:array[0..30010] of longint;  8     d,p,pre,cur,h,numh:array[0..10010] of longint;  9     q:array[0..2000010] of longint; 10     v:array[0..2010] of boolean; 11     j,x,y,f,t,ans1,ans2,len,n,m,k,i:longint; 12  13 function min(a,b:longint):longint; 14   begin 15     if a>b then exit(b) else exit(a); 16   end; 17  18 procedure add(x,y,f,w:longint); 19   begin 20     inc(len); 21     edge[len].from:=x; 22     edge[len].point:=y; 23     edge[len].next:=p[x]; 24     edge[len].flow:=f; 25     edge[len].cost:=w; 26     p[x]:=len; 27   end; 28  29 function sap:longint; 30   var tmp,x,q,u,i,j,f,neck:longint; 31   begin 32     sap:=0; 33     fillchar(numh,sizeof(numh),0); 34     fillchar(h,sizeof(h),0); 35     numh[0]:=n; 36     u:=1; 37     while h[0]
      
       n do 46         begin 47           if edge[j].flow
       
        n do 58         begin 59           dec(edge[j].flow,f); 60           inc(edge[j xor 1].flow,f); 61           i:=edge[j].point; 62           j:=cur[i]; 63         end; 64         u:=neck; 65         sap:=sap+f; 66       end; 67       q:=-1; 68       i:=p[u]; 69       while i<>-1 do 70       begin 71         x:=edge[i].point; 72         if (edge[i].flow>0) and (h[u]=h[x]+1) then 73         begin 74           q:=i; 75           break; 76         end; 77         i:=edge[i].next; 78       end; 79       if q<>-1 then 80       begin 81         cur[u]:=i; 82         x:=edge[i].point; 83         pre[x]:=u; 84         u:=x; 85       end 86       else begin 87         dec(numh[h[u]]); 88         if numh[h[u]]=0 then break; 89         tmp:=n; 90         i:=p[u]; 91         while i<>-1 do 92         begin 93           x:=edge[i].point; 94           if edge[i].flow>0 then tmp:=min(tmp,h[x]); 95           i:=edge[i].next; 96         end; 97         h[u]:=tmp+1; 98         inc(numh[h[u]]); 99         if u<>1 then u:=pre[u];100       end;101     end;102   end;103 104 function spfa:boolean;105   var f,r,i,x,y:longint;106   begin107     for i:=1 to n do108       d[i]:=max;109     d[0]:=0;110     fillchar(v,sizeof(v),false);111     fillchar(pre,sizeof(pre),255);112     v[0]:=true;113     f:=1;114     r:=1;115     q[1]:=0;116     while f<=r do117     begin118       x:=q[f];119       v[x]:=false;120       i:=p[x];121       while i<>-1 do122       begin123         y:=edge[i].point;124         if edge[i].flow>0 then125           if d[x]+edge[i].cost
        
         =max then exit(false) else exit(true);141   end;142 143 procedure mincost;144   var x,y,i,j,neck:longint;145   begin146     while spfa do147     begin148       i:=n;149       neck:=max;150       while i<>0 do151       begin152         j:=pre[i];153         neck:=min(neck,edge[j].flow);154         i:=edge[j].from;155       end;156       i:=n;157       while i<>0 do158       begin159         j:=pre[i];160         dec(edge[j].flow,neck);161         inc(edge[j xor 1].flow,neck);162         i:=edge[j].from;163       end;164       ans2:=ans2+d[n]*neck;165     end;166   end;167 168 begin169   readln(n,m,k);170   len:=-1;171   fillchar(p,sizeof(p),255);172   for i:=1 to m do173   begin174     readln(x,y,f,w[i]);175     add(x,y,f,0);176     add(y,x,0,0);177   end;178   ans1:=sap;179   t:=len;180   i:=0;181   while i<=t do182   begin183     x:=edge[i].from;184     y:=edge[i].point;185     f:=w[i div 2+1];186     add(x,y,max,f);187     add(y,x,0,-f);188     i:=i+2;189   end;190   add(0,1,k,0);191   add(1,0,0,0);192   mincost;193   writeln(ans1,' ',ans2);194 end.195 196