发布时间：2024-07-31

最小费用最大流

顾名思义，最大流中费用最小的

将EK算法的bfs换成spfa，沿着最短路增广的费用一定更小
局限：无负权环
费用：w(u,v)=-w(v,u)

cpp

const int N=5010,M=100010;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],mxf[N],pre[N];//d表示最短距离，mxf表示最大流,pre表示到i的边的编号
int n,m,S,T;
bool vis[N];
void add(int a,int b,int c,int d){
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa(){
    queue<int> q;
    memset(d,0x3f,sizeof d);
    memset(mxf,0,sizeof mxf);
    q.push(S);
    d[S]=0,mxf[S]=INF;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];~i;i=ne[i]){
            int v=e[i];
            if(f[i]&&d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
                pre[v]=i;
                mxf[v]=min(f[i],mxf[u]);
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return mxf[T]>0;
}   
void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=mxf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}
void solve(){
    cin>>n>>m>>S>>T;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<flow<<" "<<cost<<"\n";
}

最小费用最大流 ​

最小费用最大流