Description
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：
1、在不扩容的情况下，1到N的最大流；
2、将1到N的最大流增加K所需的最小扩容费用。
Input
第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。
接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
N<=1000，M<=5000，K<=10
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
Sample Output
13 19
Solution
第一问直接最大流。
第二问费用流，对每条边建一条额外的边，起点终点一样，容量为(+infty)，费用为(w_i)。然后设一个超级汇点(T)，汇点 (t)向(T)连边，费用(0)，容量(k)。
然后我比较懒，啥优化都没加...第二问直接在残余网络上跑就好了。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 2e5+10;
const int inf = 1e9;
int n,m,s,t,tot=1,cost,k;
int head[maxn],vis[maxn],dis[maxn],eu[maxn],ev[maxn],ec[maxn],ans;
struct edge{int to,nxt,w,c;}e[maxn<<1];
void add(int u,int v,int w,int c) {e[++tot]=(edge){v,head[u],w,c},head[u]=tot;}
void ins(int u,int v,int w,int c) {add(u,v,w,c),add(v,u,0,-c);}
int bfs() {
memset(vis,0,(t+1)*4);
memset(dis,63,(t+1)*4);
queue<int > q;q.push(s),dis[s]=0,vis[s]=1;
while(!q.empty()) {
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x],v;i;i=e[i].nxt)
if(e[i].w>0&&dis[v=e[i].to]>dis[x]+e[i].c) {
dis[v]=dis[x]+e[i].c;
if(!vis[v]) q.push(v),vis[v]=1;
}
}
return dis[t]<inf;
}
int dfs(int x,int f) {
vis[x]=1;
if(x==t) return cost+=dis[t]*f,f;
int used=0;
for(int i=head[x],v;i;i=e[i].nxt)
if(((v=e[i].to)==t||!vis[v])&&e[i].w>0&&dis[v]==dis[x]+e[i].c) {
int d=dfs(v,min(f-used,e[i].w));
if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;
if(used==f) break;
}
return used;
}
int max_flow() {
int flow=0;
while(bfs()) flow+=dfs(s,inf);
return flow;
}
int mcmf() {
while(bfs()) dfs(s,inf);
return cost;
}
int main() {
read(n),read(m),read(k);s=1,t=n;
for(int i=1,w;i<=m;i++) read(eu[i]),read(ev[i]),read(w),read(ec[i]),ins(eu[i],ev[i],w,0);
printf("%d ",ans=max_flow());
for(int i=1;i<=m;i++) ins(eu[i],ev[i],inf,ec[i]);
ins(n,t=n+1,k,0);
printf("%d
",mcmf());
return 0;
}