文件详细信息

下载本文件

本文件的大小为 1904 字节。

//2022-04-08
//https://www.luogu.com.cn/record/73498616
#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	char input[ARR_SIZE],*si=input,*ti=input;
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
}
using IO::read;
inline int fmo(const int x,const int P){
	return x+((x>>31)&P);
}
inline int min(const int a,const int b){
	return a<b?a:b;
}
const int maxn=5005,maxm=50005,inf=0x0f0f0f0f;
int n,m,s,t;
int head[maxn],total=1;
struct Edge{
	int to,next,flow,cost;
}e[maxm<<1];
void add(int u,int v,int w,int c){
	e[++total]=Edge{v,head[u],w,c};
	head[u]=total;
}
bool vis[maxn];
int last[maxn],dis[maxn],incf[maxn],pre[maxn];
int q[maxn+50],front,tail,qlen;
bool spfa(){
	memset(vis,0,sizeof(bool)*(n+5));
	memset(dis,15,sizeof(int)*(n+5));
	memset(incf,15,sizeof(int)*(n+5));
	q[front=tail=0]=s;
	vis[s]=true,dis[s]=0;
	while(front!=tail+1){
		int u=q[front];
		front=fmo(front+1-qlen,qlen);
		vis[u]=false;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(e[i].flow>0&&dis[v]>dis[u]+e[i].cost){
				dis[v]=dis[u]+e[i].cost;
				pre[v]=u,last[v]=i;
				incf[v]=min(incf[u],e[i].flow);
				if(!vis[v]){
					vis[v]=true;
					q[tail=fmo(tail+1-qlen,qlen)]=v;
				}
			}
		}
	}
	return dis[t]!=inf;
}
int maxflow,mincost;
void MCMF(){
	while(spfa()){
		maxflow+=incf[t];
		mincost+=incf[t]*dis[t];
		int u=t;
		while(u!=s){
			e[last[u]].flow-=incf[t];
			e[last[u]^1].flow+=incf[t];
			u=pre[u];
		}
	}
}
int main(){
	read(n),read(m),read(s),read(t);
	qlen=n+50;
	int u,v,w,c;
	for(int i=1;i<=m;i++){
		read(u),read(v),read(w),read(c);
		add(u,v,w,c),add(v,u,0,-c);
	}
	MCMF();
	printf("%d %d\n",maxflow,mincost);
	return 0;
}