众所周知SPFA死了。WC2019的课件中给出了对SPFA的各种hack。
那么费用流也不能好好用SPFA了qwq。

首先我们知道有一个johnson最短路是可以对带负权的图进行改造使得它可以跑dijk。考虑借鉴这个算法。

假设一开始的图费用都是正的，我们就可以直接跑dijk。可是一次增广之后有些边反向了qwq。那么我们还是考虑维护一个势 h[]h[]。结论是每次 h[i]+=dis[i]h[i]+=dis[i] 即可。证明：
代码：

#include<bits/stdc++.h>
#define LL long long
#define pli pair<LL,int>
using namespace std;
const int N=1e5+50;
const LL inf=0x3f3f3f3f3f3f3f3f;
int n,m,S,T,ver[N],edge[N],val[N],nxt[N],head[N],tot=1,mn[N],f[N];LL dis[N],h[N],ans1,ans2;bool vis[N];
greater<pli> cmp;
struct node{
    pli a[N];int n;
    int size(){return n;}
    void push(pli x){a[n++]=x;push_heap(a,a+n,cmp);}
    void pop(){pop_heap(a,a+n--,cmp);}
    pli top(){return *a;}
}q;
int read(){
    int x=0,c,f=1;
    while(!isdigit(c=getchar()))c=='-'?f=-1:0;
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x;
}
void add(int x,int y,int z,int v){
    ver[++tot]=y;edge[tot]=z;val[tot]=v;nxt[tot]=head[x];head[x]=tot;
    ver[++tot]=x;edge[tot]=0;val[tot]=-v;nxt[tot]=head[y];head[y]=tot;
}
bool dijk(){
    for(int i=1;i<=n;i++)h[i]+=dis[i];
    memset(dis,0x3f,sizeof(long long)*(n+1));
    memset(vis,0,n+1);
    dis[S]=0;q.push(make_pair(0,S));mn[S]=1e9;
    while(q.size()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x],y;i;i=nxt[i]){
            y=ver[i];
            if(edge[i]&&dis[y]>dis[x]+val[i]+h[x]-h[y]){
                dis[y]=dis[x]+val[i]+h[x]-h[y];
                mn[y]=min(mn[x],edge[i]);f[y]=i;
                q.push(make_pair(dis[y],y));
            }
        }
    }
    return dis[T]!=inf;
}
void dfs(){
    int x=T,k=mn[T];ans1+=k;
    for(;x!=S;x=ver[f[x]^1]){
        edge[f[x]]-=k;edge[f[x]^1]+=k;
        ans2+=1ll*k*val[f[x]];
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1,x,y,z,v;i<=m;i++){
        x=read();y=read();z=read();v=read();
        add(x,y,z,v);
    }
    while(dijk())dfs();
    printf("%lld %lld\n",ans1,ans2);
}

另：这份代码中的堆是手写的。比priority_queue快一倍。
常用的费用流算法复杂度都是假的，不过一般没人卡就是了。复杂度正确的费用流
为什么费用流不能在最短路图上多路增广？因为最短路图上仍然可能有环。故会导致不能使用当前弧优化，可能会如同爆搜。其实也是可以写的。打vis标记，出时撤回。