无限orz hzwer神牛……
第一问很简单，按数据建图，然后一遍最大流算法即可。
第二问则需要用最小费用最大流算法，主要是建图，那么可以从第一问的残留网络上继续建图，对残留网络上的每一条边建一条容量是∞费用是w的边（反向弧容量为0，费用为-w），然后建一个超级源点，从超级源向1建一条容量为k，费用为0的边，对这个图进行最小费用最大流算法。
最小费用最大流操作：
1.首先要对于这道题的图来说，有的边需要花费费用，而有的又不用，而不用扩容的边费用为0，需要扩容的边费用为w，容量无限，这就是本题这样建图的原因。
2.对于残留网络进行费用最短路SPFA算法，不用扩容的边一定会选费用为0的边，然后记录路径，找最小容量对可行路进行增流，更新ans
——hzwer
1 uses math; 2 const inf=maxlongint; 3 type node=record 4 from,go,v,c,t,next:longint; 5 end; 6 var i,n,m,k,t,u,v,w,c,s,cnt,ans:longint; 7 q,first,from,h,cur,d:array[0..10000] of longint; 8 e:array[0..50000] of node; 9 procedure ins(u,v,w,c:longint); 10 begin 11 inc(cnt); 12 e[cnt].go:=v;e[cnt].from:=u; 13 e[cnt].v:=w;e[cnt].t:=c; 14 e[cnt].next:=first[u];first[u]:=cnt; 15 end; 16 procedure insert(u,v,w,c:longint); 17 begin 18 ins(u,v,w,c);ins(v,u,0,-c); 19 end; 20 procedure ins2(u,v,w,c:longint); 21 begin 22 inc(cnt); 23 e[cnt].go:=v;e[cnt].from:=u; 24 e[cnt].v:=w;e[cnt].c:=c; 25 e[cnt].next:=first[u];first[u]:=cnt; 26 end; 27 procedure insert2(u,v,w,c:longint); 28 begin 29 ins2(u,v,w,c);ins2(v,u,0,-c); 30 end; 31 function bfs:boolean; 32 var head,tail,i,x,y:longint; 33 begin 34 head:=0;tail:=1;fillchar(h,sizeof(h),0); 35 q[1]:=s;h[s]:=1; 36 while head<tail do 37 begin 38 inc(head); 39 x:=q[head]; 40 i:=first[x]; 41 while i<>0 do 42 begin 43 y:=e[i].go; 44 if (e[i].v<>0) and (h[y]=0) then 45 begin 46 h[y]:=h[x]+1; 47 inc(tail); 48 q[tail]:=y; 49 end; 50 i:=e[i].next; 51 end; 52 end; 53 exit(h[t]<>0); 54 end; 55 function dfs(x,f:longint):longint; 56 var i,tmp,used,y:longint; 57 begin 58 if x=t then exit(f); 59 tmp:=0;used:=0; 60 i:=cur[x]; 61 while i<>0 do 62 begin 63 y:=e[i].go; 64 if (e[i].v<>0) and (h[y]=h[x]+1) then 65 begin 66 tmp:=dfs(y,min(f-used,e[i].v)); 67 dec(e[i].v,tmp); 68 inc(e[i xor 1].v,tmp); 69 inc(used,tmp); 70 if e[i].v<>0 then cur[x]:=i; 71 if used=f then exit(f); 72 end; 73 i:=e[i].next; 74 end; 75 if used=0 then h[x]:=-1; 76 exit(used); 77 end; 78 procedure dinic; 79 begin 80 while bfs do 81 begin 82 for i:=1 to n do cur[i]:=first[i]; 83 inc(ans,dfs(s,inf)); 84 end; 85 end; 86 procedure build; 87 var tmp:longint; 88 begin 89 tmp:=cnt; 90 for i:=2 to cnt do 91 if i and 1=0 then insert2(e[i].from,e[i].go,inf,e[i].t); 92 end; 93 function spfa:boolean; 94 var i,x,y,head,tail:longint; 95 v:array[0..10000] of boolean; 96 begin 97 head:=0;tail:=1; 98 for i:=1 to n do d[i]:=inf; 99 fillchar(v,sizeof(v),false); 100 q[1]:=0;d[0]:=0;v[i]:=true; 101 while head<tail do 102 begin 103 inc(head); 104 x:=q[head]; v[x]:=false; 105 i:=first[x]; 106 while i<>0 do 107 begin 108 y:=e[i].go; 109 if (e[i].v>0) and (d[x]+e[i].c<d[y]) then 110 begin 111 d[y]:=d[x]+e[i].c; 112 from[y]:=i; 113 if not(v[y]) then 114 begin 115 inc(tail); 116 q[tail]:=y; 117 v[y]:=true; 118 end; 119 end; 120 i:=e[i].next; 121 end; 122 end; 123 exit(d[n]<>inf); 124 end; 125 procedure mcf; 126 var i,x:longint; 127 begin 128 x:=inf; 129 i:=from[n]; 130 while i<>0 do 131 begin 132 x:=min(x,e[i].v); 133 i:=from[e[i].from]; 134 end; 135 i:=from[n]; 136 while i<>0 do 137 begin 138 dec(e[i].v,x); 139 inc(e[i xor 1].v,x); 140 i:=from[e[i].from]; 141 end; 142 inc(ans,x*d[n]); 143 end; 144 procedure main; 145 begin 146 cnt:=1; 147 readln(n,m,k); 148 for i:=1 to m do 149 begin 150 readln(u,v,w,c); 151 insert(u,v,w,c); 152 end; 153 ans:=0; 154 s:=1;t:=n; 155 dinic; 156 write(ans,' '); 157 ans:=0; 158 build; 159 ins(0,1,k,0); 160 while spfa do mcf; 161 writeln(ans); 162 end; 163 begin 164 main; 165 end.