lp2604 ZJOI2010 网络扩容

第一问没什么好说的。直接看第二问。
一个很直接的想法就是，在每条边上都加上一条容量为\(k\)，费用为\(c_{e}\)的边。
但是仔细一想会发现一个问题：如果s到t有多条路径的话，上述的方法就会使得流量总额过大。
有什么好方法呢？
第一个直接的想法是发现源汇之间如果有多条路径的话，那么必然是将所有的流量k全都贪心地放在花费最小的那条路径上是最优的。
但是这显然是不可能的，考虑一个残余网络非空的情况。
故而我们换一种思路：在原来所有边上额外连流量为k的边的同时，再从n向一个虚拟汇点t连一条边。这样既可完成。

#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[20005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}
int n,m,s,t,K,dis[20005],nw[20005],val[20005],fa[20005],vis[20005];
int u[20005],v[20005],w[20005],c[20005];
std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		dis[i]=INF;
		val[i]=INF;
		vis[i]=0;
	}
	q.push(s);
	dis[s]=0,vis[s]=1,fa[t]=-1;
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].c&&e[i].w>0){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;;
}

int answ=0,ansc=0;
inline void EK(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	} 
}


void init(){
	scanf("%d%d%d",&n,&m,&K);
	s=1,t=n;
	for(int i=1;i<=n+1;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",u+i,v+i,w+i,c+i);
		add(u[i],v[i],w[i],0);
	}
	EK();
	printf("%d ",answ);
	for(int i=1;i<=m;++i){
		add(u[i],v[i],INF,c[i]);
	}
	add(t,t+1,K,0);
	++t;
	EK();
	printf("%d\n",ansc);
}

int main(){
	init();
	return 0;
}