Description
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
Input
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
Output
输出文件一行包含两个整数，分别表示问题1和问题2的答案。
Sample Input
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
Sample Output
13 19
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
正解：最大流+费用流。
第一问很简单，直接跑最大流即可。第二问，对于每条边，新加一条容量为inf，费用为ci的边，n向汇点连一条容量为ans1+k，费用为0的边。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define N ()
#define il inline
#define RG register
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; struct edge{ int nt,to,flow,cap,cost; }g[]; struct node{ int u,v,w; }G[]; int head[],d[],f[],p[],fa[],q[],n,m,k,flow,cost,ans1,ans2,num=; il int gi(){
RG int x=,q=; RG char ch=getchar(); while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar(); while (ch>='' && ch<='') x=x*+ch-,ch=getchar(); return q*x;
} il void insert(RG int from,RG int to,RG int cap,RG int cost){ g[++num]=(edge){head[from],to,,cap,cost},head[from]=num; } il int bfs(RG int S,RG int T){
memset(d,,sizeof(d));
RG int h=,t=; q[t]=S,d[S]=;
while (h<t){
RG int x=q[++h];
for (RG int i=head[x];i;i=g[i].nt){
RG int v=g[i].to;
if (!d[v] && g[i].cap>g[i].flow){
q[++t]=v,d[v]=d[x]+;
if (v==T) return ;
}
}
}
return ;
} il int dfs(RG int x,RG int T,RG int a){
if (x==T || !a) return a; RG int f,flow=;
for (RG int i=head[x];i;i=g[i].nt){
RG int v=g[i].to;
if (d[v]==d[x]+ && g[i].cap>g[i].flow){
f=dfs(v,T,min(a,g[i].cap-g[i].flow));
if (!f){ d[v]=-; continue; }
g[i].flow+=f,g[i^].flow-=f;
flow+=f,a-=f; if (!a) return flow;
}
}
return flow;
} il int maxflow(RG int S,RG int T){ RG int res=; while (bfs(S,T)) res+=dfs(S,T,inf); return res; } il int spfa(RG int S,RG int T){
for (RG int i=;i<=n+;++i) d[i]=inf;
RG int h=,t=; q[t]=S,d[S]=,f[S]=inf;
while (h<t){
RG int x=q[++h];
for (RG int i=head[x];i;i=g[i].nt){
RG int v=g[i].to;
if (d[v]>d[x]+g[i].cost && g[i].cap>g[i].flow){
q[++t]=v,d[v]=d[x]+g[i].cost,fa[v]=x,p[v]=i;
f[v]=min(f[x],g[i].cap-g[i].flow);
}
}
}
if (d[T]==inf) return ; flow+=f[T],cost+=f[T]*d[T];
for (RG int x=T;x!=S;x=fa[x]) g[p[x]].flow+=f[T],g[p[x]^].flow-=f[T];
return ;
} il int mcmf(RG int S,RG int T){ flow=,cost=; while (spfa(S,T)); return cost; } il void work(){
n=gi(),m=gi(),k=gi(); RG int c;
for (RG int i=;i<=m;++i){
G[i].u=gi(),G[i].v=gi(),c=gi(),G[i].w=gi();
insert(G[i].u,G[i].v,c,),insert(G[i].v,G[i].u,,);
}
ans1=maxflow(,n); for (RG int i=;i<=num;++i) g[i].flow=;
for (RG int i=;i<=m;++i) insert(G[i].u,G[i].v,inf,G[i].w),insert(G[i].v,G[i].u,,-G[i].w);
insert(n,n+,ans1+k,),insert(n+,n,,); ans2=mcmf(,n+);
printf("%d %d\n",ans1,ans2); return;
} int main(){
File("network");
work();
return ;
}