题解：P3381 【模板】最小费用最大流

· · 题解

upd on 2025.5.10：修正证明。感谢 shihaojiacaigitcl 指出的错误！

upd on 2025.6.9：优化。

思路

直接将 EK 算法中的 BFS 函数换成 SPFA 即可。

在残留网络中，如果正向边的边权为 w(u,v)，那么反向边的边权 w(v,u) 定义为 -w(u,v)，因为如果要退流，就要把费用也退回去。

证明

正确性证明：

设 c(p) 为路径 p 的长度，后面为了区分单位费用和费用，将单位费用称为边权。

假设可行流 f 是一个最小费用流，流量为 v，且残留网络 G_f 中无负环，现在按最短路径 p 增广，得到新流 f'，流量为 v+\delta，则 \operatorname{cost}(f'-f)=c(p)\delta。假设存在一个可行流 f_n，使得 |f_n|=v+\delta，且 f_n 的费用小于 f' 的费用，考虑流差 f_n-f，因为流的分解定理，f_n-f 可以分解为若干从源到汇的路径和若干环：

因为 p 为最短路径，所以不存在 p' 的长度小于 p 的长度，所以不存在 p'，那么 f' 就是最优解。

现在证明加黑部分：

设 f_n-f 分解出来的路径分别为 p_1,p_2,...,p_k，每条路径 p_i 携带 \delta_i 的流量，使得 \sum \delta_i=\delta，则：

\operatorname{cost}(f_n-f)=\sum_{i=1}^k c(p_i)\delta_i

因为 c(p_i)\ge c(p)，所以路径部分的总费用满足：

\sum_{i=1}^k c(p_i)\delta_i\ge \sum_{i=1}^k c(p)\delta_i=c(p)\sum_{i=1}^k \delta_i=c(p)\delta

所以：

\operatorname{cost}(f_n-f)\ge c(p)\delta

这就与 f_n 的费用比 f' 的费用小而矛盾，所以这样做是正确的。

这时候有些聪明的同学就发现了：如果一条边已经流了一些流量后，那么反向边的边权就会变成负数，那么如何保证不会出现负环呢？

定义 d_u 表示 u 点的最短路径值，即代码中的 d[u]。我们假设第 k 步后没有出现负环，但是第 k+1 步后出现了负环 C，则 C 中至少包含一条新增的反向边 v\to u，反向边的费用为 -c(u,v)。假设环 C 的边权之和为其他边的费用之和 sum 加上这条边的 -c(u,v)，则 sum-c(u,v)<0，即 sum<c(u,v)。

因为我们是按照最短路径增广的，所以 d_v=d_u+c(u,v)（根据最短路径的性质），则 d_v-d_u=c(u,v)，则 sum\ge c(u,v)（因为 d_v-d_u 是按照最短路径求出来的，不可能存在更短的替代路径），与假设矛盾，所以不可能存在负环。

时间复杂度

最坏情况下，此算法的时间复杂度为 O(nmf)，其中 f 为最大流。因为每次增广增加的流量 \Delta f>0，所以最多增广 f 次。每次增广都需要一遍 SPFA，所以时间复杂度最坏为 O(nmf)。

参考代码：

#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=5010,M=100010,inf=0x3f3f3f3f;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],w[M],idx;
int q[N],d[N],pre[N],incf[N];//d表示从源点到每个点的长度，incf表示走到每个点时的最大流量
bool st[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(){
    int hh=0,tt=1;
    mems(d,0x3f);
    mems(incf,0);
    q[0]=S;
    d[S]=0;
    incf[S]=inf;//源点的流量无限制
    while(hh!=tt){
        int t=q[hh++];//出队
        if(hh==N) hh=0;//循环队列
        st[t]=false;//一个点可以多次入队
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(f[i]>0 && d[ver]>d[t]+w[i]){
                d[ver]=d[t]+w[i];//求最短路
                pre[ver]=i;//到ver的边是i这条边
                incf[ver]=min(f[i],incf[t]);
                if(!st[ver]){
                    q[tt++]=ver;//入队
                    if(tt==N) tt=0;
                    st[ver]=true;
                }
            }
        }
    }
    return (incf[T]>0);//判断汇点的流量是否大于0，等价于判断能不能到汇点
}
void EK(int &flow,int &cost){//传引用
    flow=cost=0;
    while(spfa()){
        int t=incf[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;
        }
    }
}
int main(){
    cin>>n>>m>>S>>T;
    mems(h,-1);
    while(m--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<flow<<" "<<cost;
    return 0;
}