BZOJ
Luogu
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 21 2 5 82 5 9 95 1 6 25 1 1 81 2 8 72 5 4 91 2 1 11 4 2 1Sample Output
13 1930%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
题解
第一问裸的Dinic
第二问再加入容量为K费用为W的边，可以在原图上面跑，因为是不影响的。
code
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int N = 5005;const int inf = 1e9;struct edge{int to,next,w,cost;}a[N<<2];int n,m,k,s,t,U[N],V[N],C[N],W[N],head[N],cnt=1,dep[N],cur[N],dis[N],vis[N],pe[N],ans;queue<int>Q;int gi(){ ???int x=0,w=1;char ch=getchar(); ???while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); ???if (ch=='-') w=0,ch=getchar(); ???while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); ???return w?x:-x;}void link(int u,int v,int w,int cost){ ???a[++cnt]=(edge){v,head[u],w,cost}; ???head[u]=cnt; ???a[++cnt]=(edge){u,head[v],0,-cost}; ???head[v]=cnt;}bool bfs(){ ???memset(dep,0,sizeof(dep)); ???dep[1]=1;Q.push(1); ???while (!Q.empty()) ???{ ???????int u=Q.front();Q.pop(); ???????for (int e=head[u];e;e=a[e].next) ???????????if (a[e].w&&!dep[a[e].to]) ???????????????dep[a[e].to]=dep[u]+1,Q.push(a[e].to); ???} ???return dep[n];}int dfs(int u,int flow){ ???if (u==n) ???????return flow; ???for (int &e=cur[u];e;e=a[e].next) ???????if (a[e].w&&dep[a[e].to]==dep[u]+1) ???????{ ???????????int temp=dfs(a[e].to,min(flow,a[e].w)); ???????????if (temp) {a[e].w-=temp;a[e^1].w+=temp;return temp;} ???????} ???return 0;}int Dinic(){ ???int res=0; ???while (bfs()) ???{ ???????for (int i=1;i<=n;i++) cur[i]=head[i]; ???????while (int temp=dfs(1,inf)) res+=temp; ???} ???return res;}bool spfa(){ ???memset(dis,63,sizeof(dis)); ???dis[n+1]=0;Q.push(n+1); ???while (!Q.empty()) ???{ ???????int u=Q.front();Q.pop(); ???????for (int e=head[u];e;e=a[e].next) ???????{ ???????????int v=a[e].to; ???????????if (a[e].w&&dis[v]>dis[u]+a[e].cost) ???????????{ ???????????????dis[v]=dis[u]+a[e].cost;pe[v]=e; ???????????????if (!vis[v]) vis[v]=1,Q.push(v); ???????????} ???????} ???????vis[u]=0; ???} ???if (dis[n]==dis[0]) return false; ???int sum=inf; ???for (int i=n;i!=n+1;i=a[pe[i]^1].to) ???????sum=min(sum,a[pe[i]].w); ???for (int i=n;i!=n+1;i=a[pe[i]^1].to) ???????a[pe[i]].w-=sum,a[pe[i]^1].w+=sum; ???ans+=dis[n]*sum; ???return true;}int main(){ ???n=gi();m=gi();k=gi(); ???for (int i=1;i<=m;i++) ???{ ???????U[i]=gi();V[i]=gi(); ???????C[i]=gi();W[i]=gi(); ???????link(U[i],V[i],C[i],0); ???} ???link(n+1,1,k,0); ???printf("%d ",Dinic()); ???for (int i=1;i<=m;i++) ???????link(U[i],V[i],k,W[i]); ???while (spfa()); ???printf("%d\n",ans); ???return 0;}