[ZJOI2010]网络扩容

题目描述
给定一张有向图，每条边都有一个容量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 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 复制
13 19
说明/提示
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10

对于第一问直接最大流即可，费用加为0即可。

第二问我们利用第一问的残量网络，在往里面加边，和最大流加的边一样，只不过流量变为k，费用变为题目给出的值，同时我们要保证流量不会超过k，所以我们连一条n到n+1流量为k，费用为0的边，跑1到n+1的费用流即可。

AC代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
int n,m,k,s,t,a[N],b[N],c[N],d[N],v[N],e[N],dst[N];
int head[N],nex[N],to[N],w[N],flow[N],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int bfs(){
	queue<int> q;	int vis[N]={0};	q.push(s);	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&!vis[to[i]]){
				vis[to[i]]=1;	q.push(to[i]);
				v[to[i]]=u;	e[to[i]]=i;
				if(to[i]==t)	return 1;
			}
		}
	}
	return 0;
}
int spfa(){
	memset(dst,inf,sizeof dst);	queue<int> q;	q.push(s);	dst[s]=0;
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&dst[to[i]]>dst[u]+w[i]){
				dst[to[i]]=dst[u]+w[i];
				v[to[i]]=u;	e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return dst[t]!=inf;
}
int EK(int k){
	int res=0;
	while((k?spfa():bfs())){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		if(k)	res+=mi*dst[t];	else	res+=mi;
	}
	return res;
}
signed main(){
	cin>>n>>m>>k;	s=1;	t=n;
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];	add(a[i],b[i],c[i],0);
	}
	cout<<EK(0)<<' ';
	for(int i=1;i<=m;i++)	add(a[i],b[i],k,d[i]);
	t=n+1;
	add(n,t,k,0);
	cout<<EK(1)<<endl;
	return 0;
}