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[100010]; struct node{ int u,v,w; }G[5010]; int head[1010],d[1010],f[1010],p[1010],fa[1010],q[1000010],n,m,k,flow,cost,ans1,ans2,num=1; il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,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,0,cap,cost},head[from]=num; } il int bfs(RG int S,RG int T){ memset(d,0,sizeof(d)); RG int h=0,t=1; q[t]=S,d[S]=1; 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]+1; if (v==T) return 1; } } } return 0; } il int dfs(RG int x,RG int T,RG int a){ if (x==T || !a) return a; RG int f,flow=0; for (RG int i=head[x];i;i=g[i].nt){ RG int v=g[i].to; if (d[v]==d[x]+1 && g[i].cap>g[i].flow){ f=dfs(v,T,min(a,g[i].cap-g[i].flow)); if (!f){ d[v]=-1; continue; } g[i].flow+=f,g[i^1].flow-=f; flow+=f,a-=f; if (!a) return flow; } } return flow; } il int maxflow(RG int S,RG int T){ RG int res=0; while (bfs(S,T)) res+=dfs(S,T,inf); return res; } il int spfa(RG int S,RG int T){ for (RG int i=1;i<=n+1;++i) d[i]=inf; RG int h=0,t=1; q[t]=S,d[S]=0,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 0; 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]^1].flow-=f[T]; return 1; } il int mcmf(RG int S,RG int T){ flow=0,cost=0; while (spfa(S,T)); return cost; } il void work(){ n=gi(),m=gi(),k=gi(); RG int c; for (RG int i=1;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,0),insert(G[i].v,G[i].u,0,0); } ans1=maxflow(1,n); for (RG int i=2;i<=num;++i) g[i].flow=0; for (RG int i=1;i<=m;++i) insert(G[i].u,G[i].v,inf,G[i].w),insert(G[i].v,G[i].u,0,-G[i].w); insert(n,n+1,ans1+k,0),insert(n+1,n,0,0); ans2=mcmf(1,n+1); printf("%d %d ",ans1,ans2); return; } int main(){ File("network"); work(); return 0; }