题目描述
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。
输入输出格式
输入格式：
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
输出格式：
输出文件一行包含两个整数，分别表示问题1和问题2的答案。
输入输出样例
输入样例#1：
5 8 21 2 5 82 5 9 95 1 6 25 1 1 81 2 8 72 5 4 91 2 1 11 4 2 1
输出样例#1：
13 19
说明
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
题解
话说其实不用新建图的……我看到好几位大佬的做法都是0.5倍经验+码量巨大的……
实际上只要直接跑一个费用流就行了。对于第一问，我们直接连边，然后令费用为$0$，跑一遍，输出最大流即可
对于第二问，只要在原来的每条边上再连一条边，容$inf$费为扩边费用，然后$k$的限制只要再建一个源点往$1$连容$k$费$0$的边。在残量网络上再跑一遍，输出最小费用即可
考虑为什么这样做是对的。因为要跑最小费用最大流，而原图是无花费的最大流，那么只要在此残量网络上继续增广，就可以保证跑出最小费用了
1 //minamoto 2 #include3 #include 4 #include 5 #include 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 inline int read(){11 #define num ch-'0'12 char ch;bool flag=0;int res;13 while(!isdigit(ch=getc()))14 (ch=='-')&&(flag=true);15 for(res=num;isdigit(ch=getc());res=res*10+num);16 (flag)&&(res=-res);17 #undef num18 return res;19 }20 const int N=1005,M=50005;21 struct node{22 int u,v,f,e;23 node(){}24 node(int u,int v,int f,int e):u(u),v(v),f(f),e(e){}25 }E[M];26 int ver[M],Next[M],head[N],edge[M],flow[M],tot=1;27 int dis[N],disf[N],vis[N],Pre[N],last[N];28 int n,m,k,s,t,maxflow,mincost;29 queue q;30 inline void add(int u,int v,int f,int e){31 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,flow[tot]=f,edge[tot]=e;32 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,flow[tot]=0,edge[tot]=-e;33 }34 bool spfa(){35 memset(dis,0x3f,sizeof(dis));36 q.push(s),dis[s]=0,disf[s]=inf,Pre[t]=-1;37 while(!q.empty()){38 int u=q.front();q.pop();vis[u]=0;39 for(int i=head[u];i;i=Next[i]){40 int v=ver[i];41 if(flow[i]&&dis[v]>dis[u]+edge[i]){42 dis[v]=dis[u]+edge[i],Pre[v]=u,last[v]=i;43 disf[v]=min(disf[u],flow[i]);44 if(!vis[v]) vis[v]=1,q.push(v);45 }46 }47 }48 return ~Pre[t];49 }50 void dinic(){51 while(spfa()){52 int u=t;maxflow+=disf[t],mincost+=disf[t]*dis[t];53 while(u!=s){54 flow[last[u]]-=disf[t];55 flow[last[u]^1]+=disf[t];56 u=Pre[u];57 }58 }59 }60 int main(){61 n=read(),m=read(),k=read();62 s=1,t=n;63 for(int i=1;i<=m;++i){64 int u=read(),v=read(),f=read(),e=read();65 E[i]=node(u,v,f,e);66 add(u,v,f,0);67 }68 dinic();69 printf("%d ",maxflow);70 for(int i=1;i<=m;++i){71 int u=E[i].u,v=E[i].v,e=E[i].e;72 add(u,v,inf,e);73 }74 s=0;75 add(s,1,k,0);76 dinic();77 printf("%d\n",mincost);78 return 0;79 }