BZOJ 1834 ZJOI2010 network 网络扩容

#include <bits/stdc++.h>
#define ll long long
#define inf 1e9+10
using namespace std;
inline int read(){
	int x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int MAXN=1e5+10;
struct node{
	int y,next,back,flow,w;
}e[MAXN];
int len,linkk[MAXN],head,tail,level[1100],s,t,n,m,x[MAXN],y[MAXN],f[MAXN],c[MAXN],dis[1100],ans,vis[1100],q[MAXN],k;
inline void insert(int x,int y,int f,int c){
	e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;e[len].flow=f;e[len].back=len+1;e[len].w=c;
	e[++len].y=x;e[len].next=linkk[y];linkk[y]=len;e[len].flow=0;e[len].back=len-1;e[len].w=-c;
}
namespace dinicc{
	inline bool getlevel(){
		head=tail=0;
		memset(level,-1,sizeof(level));
		level[s]=0;q[++tail]=s;
		while(head<tail){
			int tn=q[++head];
			for(int i=linkk[tn];i;i=e[i].next){
				if(level[e[i].y]==-1&&e[i].flow){
					level[e[i].y]=level[tn]+1;
					q[++tail]=e[i].y;
				}
			}
		}
		return level[t]>=0;
	}
	inline int getmaxflow(int x,int flow){
		if(x==t) return flow;
		int f=0,d;
		for(int i=linkk[x];i;i=e[i].next){
			if(e[i].flow&&level[e[i].y]==level[x]+1){
				if(d=getmaxflow(e[i].y,min(e[i].flow,flow-f))){
					f+=d;e[i].flow-=d;e[e[i].back].flow+=d;
					if(f==flow) return f;
				}
			}
		}
		if(!f) level[x]=-1;
		return f;
	}
	inline int dinic(){
		int ans=0,d;
		while(getlevel()){
			while(d=getmaxflow(s,inf)) ans+=d;
		}
		return ans;
	}
}
namespace zkww{
	inline bool getdis(){
		memset(vis,0,sizeof(vis));
		memset(dis,10,sizeof(dis));
		dis[t]=0;
		deque<int>q;q.push_back(t);
		while(!q.empty()){
			int tn=q.front();q.pop_front();
			for(int i=linkk[tn];i;i=e[i].next){
				if(dis[tn]-e[i].w<dis[e[i].y]&&e[e[i].back].flow){
					dis[e[i].y]=dis[tn]-e[i].w;
					if(!vis[e[i].y]){
						vis[e[i].y]=1;
						if(!q.empty()&&dis[e[i].y]<dis[q.front()]) q.push_front(e[i].y);
						else q.push_back(e[i].y);
					}
				}
			}
			vis[tn]=0;
		}
		return dis[s]<168430090;
	}
	inline int getcost(int x,int flow){
        int f=0,d;vis[x]=1;
		if(x==t) return flow;
		for(int i=linkk[x];i;i=e[i].next){
			if(e[i].flow&&dis[e[i].y]==dis[x]-e[i].w&&!vis[e[i].y]){
				if(d=getcost(e[i].y,min(flow-f,e[i].flow))){
					f+=d;e[i].flow-=d;e[e[i].back].flow+=d;
					ans+=e[i].w*d;
					if(f==flow) return f;
				}
			}
		}
		return f;
	}
	inline void zkw(){
		while(getdis()){
			vis[t]=1;
			while(vis[t]){
				memset(vis,0,sizeof(vis));
				getcost(s,inf);
			}
		}
	}
}
void build(){
	s=0;t=n;
	insert(s,1,k,0);
	for(int i=1;i<=m;i++){
		insert(x[i],y[i],inf,c[i]);
	}
}
int main(){
	using namespace dinicc;
	using namespace zkww;
	n=read();m=read();k=read();s=1;t=n;
	for(int i=1;i<=m;i++){
		x[i]=read();y[i]=read();f[i]=read();c[i]=read();
		insert(x[i],y[i],f[i],0);
	}
	ans=dinic();
	cout<<ans<<' ';
	build();ans=0;
	zkw();
	cout<<ans<<endl;
	return 0;
}