最小费用是最大流基础上的
那么就用spfa代替Ek的bfs就行
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,t;
int u,v,w,c;
const int maxn=5001;
const int maxm=50001;
int head[maxn];
struct b{
int to;
int ne;
int v;
int c;
}ed[maxm*2];
int p=1;
void add(int f,int t,int v,int c){
ed[++p].ne=head[f];ed[p].to=t;ed[p].v=v;head[f]=p;ed[p].c=c;
ed[++p].ne=head[t];ed[p].to=f;ed[p].v=0;head[t]=p;ed[p].c=-c;
}
queue<int> q;
int inf=(1<<25);
int vis[maxn];
int dis[maxn];
int exf[maxn];
int pre[maxn];
int last[maxn];
int znx;
int Aimee;
bool spfa(){
memset(vis,0,sizeof(vis));
memset(dis,0x7f,sizeof(dis));
memset(exf,0x7f,sizeof(exf));
while(!q.empty()){
q.pop();
}
q.push(s);
dis[s]=0;vis[s]=1,pre[t]=-1;
while(!q.empty()){
int x=q.front();
vis[x]=0;
q.pop();
for(int i=head[x];i;i=ed[i].ne){
if(ed[i].v>0&&dis[ed[i].to]>dis[x]+ed[i].c){
dis[ed[i].to]=dis[x]+ed[i].c;
pre[ed[i].to]=i;
exf[ed[i].to]=min(exf[x],ed[i].v);
if(!vis[ed[i].to]){
q.push(ed[i].to);
vis[ed[i].to]=1;
}
}
}
}
return pre[t]!=-1;
}
void up(){
znx+=exf[t];
Aimee+=exf[t]*dis[t];
int now=t;
while(now!=s){
ed[pre[now]].v-=exf[t];
ed[pre[now]^1].v+=exf[t];
now=ed[pre[now]^1].to;
}
return ;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&u,&v,&w,&c);
add(u,v,w,c);
}
while(spfa()){
up();
}
cout<<znx<<" "<<Aimee;
return 0;
}