Aimee

最小费用是最大流基础上的

那么就用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;
}