类 Dinic 算法

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=1e5+5,INF=0x3f3f3f3f;
int head[N],cur[N],to[M],nxt[M],dis[N],val[M],tot=1,cost[M];
bool vis[N];
bool adj[N][N];
void add(int u,int v,int c,int w){
	nxt[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	val[tot]=c;
	cost[tot]=w;
}
void addedge(int u,int v,int c,int w){
	add(u,v,c,w);
	add(v,u,0,-w);
}
bool spfa(int s,int t){
	memset(dis,0x3f,sizeof(dis));
	queue<int>que;
	que.push(s);
	dis[s]=0;
	vis[s]=1;
	cur[s]=head[s];
	while(!que.empty()){
		int u=que.front();
		que.pop();
		vis[u]=0;
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(val[i]&&dis[v]>dis[u]+cost[i]){
				dis[v]=dis[u]+cost[i];
				cur[v]=head[v];
				if(!vis[v])
					que.push(v),vis[v]=1;
			}
		}
	}
	return dis[t]!=INF;
}
int Cost;
int dfs(int u,int ret,int s,int t){
	if(u==t||ret==0) return ret;
	int Flow=0;
	vis[u]=1;
	for(int i=cur[u];i&&ret;i=nxt[i]){
		int v=to[i];
		cur[u]=i;
		if(!vis[v]&&val[i]>0&&dis[v]==dis[u]+cost[i]){
			int f=dfs(v,min(ret,val[i]),s,t);
			if(f==0) vis[v]=0;
			Cost+=f*cost[i];
			val[i]-=f;
			val[i^1]+=f;
			Flow+=f;
			ret-=f;
		}
	}
	vis[u]=0;
	return Flow;
}
int mcmf(int s,int t){
	int Flow=0;
	while(spfa(s,t)){
		Flow+=dfs(s,INF,s,t);
	}
	return Flow;
}
int main(){
//	freopen("P3381_8.in","r",stdin);
	int n,m,s,t;
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		int u,v,c,w;
		scanf("%d %d %d %d",&u,&v,&c,&w);
		if(!adj[u][v])
			addedge(u,v,c,w);
		adj[u][v]=1;
	}
	printf("%d",mcmf(s,t));
	printf(" %d",Cost);
	return 0;
}