网络流裸体 

第一问最大流跑一跑

第二问新建一个点连边到1 容量k费用0 再对所有的边复制一条边出来 容量为inf 费用为w

然后跑最小费用最大流

这题最大流用ek可过

#include <cstdio>
#include <algorithm>
#include <cstring>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
const int N=100010,inf=308888888;
struct Ask{
	int u,v,c,w;
	void read2(){read(u),read(v);read(c);read(w);}
}ask[N];
int n,m,c[N],to[N],nxt[N],now[N],cap[N],tail=1,q[N],from[N],dis[N],inq[N],k,ans;
void add(int u,int v,int ci,int capi){
	to[++tail]=v;nxt[tail]=now[u];now[u]=tail;c[tail]=ci;cap[tail]=capi;
	to[++tail]=u;nxt[tail]=now[v];now[v]=tail;c[tail]=-ci;cap[tail]=0;
}
bool spfa(int s,int t){
	int l=0,r=0;
	clr(from);clr(inq);
	for(int i=1;i<=n+2;i++) dis[i]=inf;
	q[++r]=s;dis[s]=0;inq[s]=1;
	while(l<r){
		int u=q[(++l)%N];inq[u]=0;
		for(int i=now[u];i;i=nxt[i]) if(cap[i]>0 && dis[to[i]]>dis[u]+c[i]){
			int v=to[i];
			dis[v]=dis[u]+c[i];
			from[v]=i;
			if(!inq[v]) q[(++r)%N]=v;
		}
	}
	return dis[t]!=inf;
}
int augument(int s,int t,int type){
	int fl=inf,ret=0;
	for(int tmp=t;tmp!=s;){
		int e=from[tmp];
		fl=min(cap[e],fl);
		tmp=to[e^1];
	}
	for(int tmp=t;tmp!=s;){
		int e=from[tmp];
		cap[e]-=fl;cap[e^1]+=fl;
		ret+=fl*c[e];
		tmp=to[e^1];
	}
	return type?ret:fl;
}
int main(){
	//freopen("1834.in","r",stdin);freopen("1834.out","w",stdout);
	read(n);read(m);read(k);
	for(int i=1;i<=m;i++) {
		ask[i].read2();
		add(ask[i].u,ask[i].v,0,ask[i].c);
	}
	while(spfa(1,n)) ans+=augument(1,n,0);
	printf("%d ",ans);ans=0;
	for(int i=1;i<=m;i++) add(ask[i].u,ask[i].v,ask[i].w,inf);
	add(n+1,1,0,k);
	while(spfa(n+1,n)) 	ans+=augument(n+1,n,1);
	printf("%d",ans);
}