首先先跑裸的最大流，然后加边，在残余网络上跑费用流
比较水
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 38 begin 39 if u=n then 40 begin 41 i:=1; 42 j:=cur[i]; 43 neck:=i; 44 f:=edge[j].flow; 45 while i<>n do 46 begin 47 if edge[j].flow<f then 48 begin 49 f:=edge[j].flow; 50 neck:=edge[j].from; 51 end; 52 i:=edge[j].point; 53 j:=cur[i]; 54 end; 55 i:=1; 56 j:=cur[i]; 57 while i<>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 begin 107 for i:=1 to n do 108 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 do 117 begin 118 x:=q[f]; 119 v[x]:=false; 120 i:=p[x]; 121 while i<>-1 do 122 begin 123 y:=edge[i].point; 124 if edge[i].flow>0 then 125 if d[x]+edge[i].cost<d[y] then 126 begin 127 d[y]:=d[x]+edge[i].cost; 128 pre[y]:=i; 129 if not v[y] then 130 begin 131 v[y]:=true; 132 inc(r); 133 q[r]:=y; 134 end; 135 end; 136 i:=edge[i].next; 137 end; 138 inc(f); 139 end; 140 if d[n]>=max then exit(false) else exit(true); 141 end; 142 143 procedure mincost; 144 var x,y,i,j,neck:longint; 145 begin 146 while spfa do 147 begin 148 i:=n; 149 neck:=max; 150 while i<>0 do 151 begin 152 j:=pre[i]; 153 neck:=min(neck,edge[j].flow); 154 i:=edge[j].from; 155 end; 156 i:=n; 157 while i<>0 do 158 begin 159 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 begin 169 readln(n,m,k); 170 len:=-1; 171 fillchar(p,sizeof(p),255); 172 for i:=1 to m do 173 begin 174 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 do 182 begin 183 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