文件详细信息

下载本文件

本文件的大小为 2881 字节。

#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)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	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();
	}
	void getstr(char*str){
		char ch=gc();
		while(ch=='\r'||ch=='\n'||ch==' '||ch=='\t')ch=gc();
		while(ch!='\r'&&ch!='\n'&&ch!=' '&&ch!='\t'&&ch!=EOF)*(str++)=ch,ch=gc();
		*str='\0';
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
	void putstr(const char*str){
		while(*str!='\0')pc(*(str++));
	}
}
using IO::read;
using IO::getstr;
using IO::write;
using IO::putstr;
template<typename T>
inline T min(const T a,const T b){
	return a<b?a:b;
}
inline int qmod(const int x,const int P){
	return x+((x>>31)&P);
}
const int maxn=5000,maxm=50000,inf=0x3f3f3f3f;
int n,m,s,t;
int head[maxn+1],cur[maxn+1],total=1;
struct Edge{
	int to,next,flow,cost;
}e[maxm*2+2];
void add(const int u,const int v,const int w,const int c){
	e[++total]=Edge{v,head[u],w,c};
	head[u]=total;
}
int dis[maxn+1],q[maxn+10],qlen,front,tail;
bool vis[maxn+1];
bool spfa(){
	memset(dis+1,63,sizeof(int)*n);
	front=1,tail=0;
	q[tail=qmod(tail+1-qlen,qlen)]=s;
	dis[s]=0;
	vis[s]=true;
	while(front!=qmod(tail+1-qlen,qlen)){
		const int u=q[front];
		vis[u]=false;
		front=qmod(front+1-qlen,qlen);
		for(int i=head[u];i;i=e[i].next){
			const int v=e[i].to;
			if(e[i].flow&&dis[v]>dis[u]+e[i].cost){
				dis[v]=dis[u]+e[i].cost;
				if(!vis[v]){
					q[tail=qmod(tail+1-qlen,qlen)]=v;
					vis[v]=true;
				}
			}
		}
	}
	return dis[t]!=inf;
}
int maxflow,mincost;
int dfs(const int u,int in){
	if(u==t)return in;
	vis[u]=true;
	int out=0;
	for(int&i=cur[u];i;i=e[i].next){
		const int v=e[i].to;
		if(!vis[v]&&e[i].flow&&dis[v]==dis[u]+e[i].cost){
			const int res=dfs(v,min(in,e[i].flow));
			in-=res;
			out+=res;
			e[i].flow-=res;
			e[i^1].flow+=res;
			mincost+=res*e[i].cost;
			if(!in)break;
		}
	}
	if(!out)dis[u]=inf;
	vis[u]=false;
	return out;
}
void ssp(){
	while(spfa()){
		memcpy(cur+1,head+1,sizeof(int)*n);
		maxflow+=dfs(s,0x7fffffff);
	}
}
int main(){
	read(n),read(m),read(s),read(t);
	qlen=n+5;
	for(int i=1,u,v,w,c;i<=m;i++){
		read(u),read(v),read(w),read(c);
		add(u,v,w,c),add(v,u,0,-c);
	}
	ssp();
	write(maxflow),pc(' '),write(mincost),pc('\n');
	return 0;
}