玄关求条

#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,int> 
const int inf=1e9+10;
const int N=5e3+10,M=1e5+10;

int n,m,s,t;
struct node{
	int to,nxt,f,w; 
}edge[M];
int head[N],cnt=1;

void add(int u,int v,int f,int w){
	edge[++cnt]=node{v,head[u],f,w},head[u]=cnt;
	edge[++cnt]=node{u,head[v],0,-w},head[v]=cnt;
}

int h[N],vis[N];
int lst[N],dis[N],flow[N];
int max_flow,min_cost;

void spfa(){
	queue<int> q;
	memset(h,0x7f,sizeof(h));
	h[s]=0,vis[s]=1,q.push(s);
	while(!q.empty()){
		int u=q.front(); q.pop();
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to,w=edge[i].w;
			if(edge[i].f&&h[v]>h[u]+w){
				h[v]=h[u]+w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			} 
		} 
	}
}

bool dij(){
	priority_queue<pr,vector<pr>,greater<pr> >q;
	for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
	dis[s]=0,flow[s]=inf;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].to,w=edge[i].w+h[u]-h[v],f=edge[i].f;
			if(f&&dis[v]>dis[u]+w){
				flow[v]=min(flow[u],f);
				dis[v]=dis[u]+w;
				lst[v]=i;
				q.push(make_pair(dis[v],v));
			}
		} 
	}
	return (dis[t]!=inf);
}

signed main(){
	//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,f,c;
		cin>>u>>v>>f>>c;
		add(u,v,f,c);
	}
	spfa();
	while(dij()){
		max_flow+=flow[t];
		min_cost+=flow[t]*(dis[t]-h[s]+h[t]);
		for(int i=t;i!=s;i=edge[lst[i]^1].to){
			edge[lst[i]].f-=flow[t];
			edge[lst[i]^1].f+=flow[t];
		} 
		for(int i=1;i<=n;i++) h[i]+=dis[i];
	}
	cout<<max_flow<<" "<<min_cost<<'\n';
	return 0;
}