原题链接：网络扩容
分析：
题目两个小问，第一个小问就不说了，重点是第二问。
第二小问要求扩容，考虑扩容后有什么影响：
- 从源点出发的流量增加了k
- 进入汇点的流量增加了k
那么，这道题写完了。
由于第一小问跑出了最大流，那么剩下的残量网络必定不能通行流，那么我们只需要建立一个超级源，再重新建立各边，把各边的费用设为扩容费用，容量设为无穷大。
那么为什么这样可行呢？首先，根据费用流的计算方法，如果有边的费用为0，那么肯定优先走这条边，流量跑满了才会考虑费用高的边。那么肯定会优先跑完费用为0边，大边的容量为无穷大，可以无限扩容，扩容的费用就是流量×单位费用。
那么只需要在残量网络上跑一边费用流即可。
代码
以下代码bzoj能ac，洛谷0分，样例都过不去。。
为啥要放上来？？不想写了！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int inf=(1<<31)-1,N=1009,M=500009;
struct info{
int u;int v;int c;int w;
} info[5009];
int n,m,k,flow,maxflow,s,t,mincost,v[N],incf[N],pre[N];
int ver[M],head[N],next[M],edge[M],tot=1,d[N],cost[M];
queue <int> q;
void add(int x,int y,int c,int val){
ver[++tot]=y;edge[tot]=c;next[tot]=head[x];head[x]=tot,cost[tot]=val;
//if(tot==28)cout<<x<<" "<<y<<" "<<c<<" "<<val<<ver[tot]<<endl;
ver[++tot]=x;edge[tot]=0;next[tot]=head[y];head[y]=tot,cost[tot]=-val;
}
bool bfs();
bool spfa();
void update();
int dinic(int x,int flow);
void work1();
void work2();
int main()
{
//freopen("data.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
s=1;t=n;
for(int i=1;i<=m;i++)
scanf("%d%d%d%d",&info[i].u,&info[i].v,&info[i].c,&info[i].w);
work1();
work2();
return 0;
}
void work1(){
for(int i=1;i<=m;i++)
add(info[i].u,info[i].v,info[i].c,0);
while(bfs())
while(flow=dinic(s,inf))maxflow+=flow;
printf("%d\n",maxflow);
}
bool bfs(){
memset(d,0,sizeof(d));
while(q.size())q.pop();
q.push(s);d[s]=1;
while(q.size()){
int x=q.front();q.pop();
for(int i=head[x];i;i=next[i]){
int y=ver[i];
if(edge[i]&&!d[y]){
q.push(y);
d[y]=d[x]+1;
if(y==t)return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t)return flow;
int res=flow,k;
for(int i=head[x];i&&res;i=next[i]){
int y=ver[i];
if(edge[i]&&d[y]==d[x]+1){
k=dinic(y,min(flow,edge[i]));
if(!k)d[y]=0;
edge[i]-=k;
edge[i^1]+=k;
res-=k;
}
}
return flow-res;
}
void work2(){
add(0,s,k,0);
s=0;
for(int i=1;i<=m;i++)
add(info[i].u,info[i].v,inf,info[i].w);
while(spfa())
update();
printf("%d\n",mincost);
}
bool spfa(){
memset(d,0x3f,sizeof(d));
memset(incf,0x3f,sizeof(incf));
memset(v,0,sizeof(v));
while(q.size())q.pop();
q.push(s);v[s]=1;d[s]=0;
while(q.size()){
int x=q.front();
v[x]=0;q.pop();
for(int i=head[x];i;i=next[i]){
if(edge[i]<=0)continue;
int y=ver[i];
if(d[y]>d[x]+cost[i]){
d[y]=d[x]+cost[i];
//if(x==0&&y==1)cout<<edge[i]<<endl;
incf[y]=min(incf[x],edge[i]);
//if(y==t)cout<<cost[i]<<endl;
pre[y]=i;
if(!v[y])v[y]=1,q.push(y);
}
}
}
if(d[t]==0x3f3f3f3f)return false;
return true;
}
void update(){
int x=t;
while(x!=s){
int i=pre[x];
edge[i]-=incf[t];
edge[i^1]+=incf[t];
mincost+=incf[t]*cost[i];
//cout<<cost[i]<<endl;
x=ver[i^1];
}
}