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

LEWISAK · 2025-05-22 15:12:04 · 题解

我的博客

upd on 2025.11.10：添加了多路增广的代码。

费用流

定义

就是对每一条边加了个权值 w_{u,v}，定义对于一条边的花费为 w_{u,v}\times f_{u,v}，求：在满足最大流的前提下使得花费最小/大的花费和流量。

Dinic/EK 求费用流

把它们算法中的 bfs 换为 spfa 即可，无需脑子即可实现，这篇侧重点不在这里就不贴代码了昂

ISAP 求费用流（

经过了不知道多久的钻研后，我认为这个算法反正我是难以实现了😭。

ISAP 不能直接求费用流的原因是因为它最核心的层数思想失效了—如果你想要延续这个思想，你就需要在某个点在走第 k 短路的情况下被榨干后把它的标号改为从 k+1 更新出来的，这个思路一眼让复杂度伪。

有兴趣的研究新算法的请移步，可能我的一些思考会对你有帮助吧。

原始对偶算法求最小费用最大流

这就是神！~~要水估值写详细点~~。

在讲解这之前，我们要先介绍另一个算法。

Johnson 全源最短路径算法

这个算法用来求什么看算法名都能看出来吧。

我们注意到 dij 的复杂度非常的优秀，但是如果有负边权它就死了。

所以我们考虑对原图的边权进行处理使得在不改变答案的情况下使得边权非负。

一个伪的没边的方法是把所有边权都加上一个定值后统计答案时减去。

这个方法伪的地方是因为我们最短路时会受这个定值的影响，每多走一条边就会让距离多一个不该多的定值。

算法实现

新建一个虚拟点 0，并将它与所有点连一条边权为 0 的边，然后以 0 为起点跑 spfa 后对于边 u\to v 的边权 w_{u,v} 修改为 w_{u,v}+h_{u}-h_{v}。

正确性证明

我们注意到修改边权后对于一条路径 s\to x_1\to x_2\to\dots\to x_n\to t 的长度为：

\begin{aligned} &~~~~~~w_{s,x_1}+h_s-h_{x_1}+w_{x_1,x_2}+h_{x_1}-h_{x_2}+\dots+w_{x_n,t}+h_{x_n}-h_{t}\\ &\Rightarrow w_{s,x_1}+w_{x_1,x_2}+\dots+w_{x_n,t}+h_s-h_{t} \end{aligned}

也就是说相较于原路径，我们多了 h_s-h_t 的长度，但这个显然是定值，减掉即可。

然后我们还要证明关键的性质：所有边权为正。

注意到一个显然的事情 h_u+w_{u,v} 我们可以理解是从 0 到 v 的最短路但必须经过 u 的长度，而 h_v 就是从 0 到 v 最短路长度，所以有 h_v\le h_u+w_{u,v}，也就是 w_{u,v}+h_u-h_v 非负，也就是边权非负了！。

那有的小朋友就要问了：这个算法和最小费用最大流有什么关系呢？

我们可以先像 Johnson 一样对边权进行处理，但是问题是我们的增广会改变图的形态，所以我们要对 h 动态处理。

先直接说结论：可以对 h_i 加上 s\leadsto i 的最短路长度 d_i。

首先我们刚刚证的第一个东西显然不需要重新证明，而且网络流上甚至因为我们只需要知道增广路是那条，所以连 h_s-h_t 都不用减了！

现在证明边权非负：

对于增广路的边，因为它在最短路上，所以有：
\begin{aligned} d_i+(w_{i,j}+h_i-h_j)&=d_j\\ w_{i,j}+(d_i+h_i)-(h_j+d_j)&=0 \end{aligned}
于是非负。
对于增广后多的边（增广路上边的反向边）：
\begin{aligned} d_i+(w_{i,j}+h_i-h_j)&=d_j\\ d_i-(w_{j,i}-h_i+h_j)&=d_j\\ (w_{j,i}-h_i+h_j)+d_j-d_i&=0\\ w_{j_i}-(h_i+d_i)+(h_j+d_j)&=0 \end{aligned}
其中第一行推出第二行的原因是反向边的边权为正向边边权的相反数，于是非负。
对于其他边，和 Johnson 最后一步证明时类似的，有：
\begin{aligned} d_i+(w_{i,j}+h_i-h_j)&\ge d_j\\ w_{i,j}+(h_i+d_i)-(h_j+d_j)&\ge 0 \end{aligned}
于是非负。

然后就证完了🎉

代码

在神秘模拟赛题目中，可以看出多路和单路增广的效率相差甚远，所以不要省那一个 dfs。

单路增广

这个通常慢得多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace kong{bool st;}
namespace zhu{
int tot=1,head[1001000],answ,ansc,n,m,s,t,h[1001000],dis[1001000],vis[1001000];
queue<int> q;
struct node{
    int v,id;
    bool operator<(const node& a)const{
        return v>a.v;
    }
};
priority_queue<node> qq;
struct{
    int nxt,to,w,c;
}e[2002000],fr[2002000];
//fr 记录找到的增广路
void add(int u,int v,int w,int c){
    e[++tot]={head[u],v,w,c};
    head[u]=tot;
    e[++tot]={head[v],u,0,-c};
    head[v]=tot;
    return;
}
void spfa(){
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof vis);
    memset(h,0x3f,sizeof h);
    h[s]=0;vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to,c=e[i].c;
            if(e[i].w&&h[v]>h[x]+c){
                h[v]=h[x]+c;
                if(vis[v]) continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
}
bool dij(){
    while(!qq.empty()) qq.pop();
    for(int i=1;i<=n;i++) vis[i]=0,dis[i]=1e18;
    dis[s]=0;
    qq.push({0,s});
    while(!qq.empty()){
        int x=qq.top().id;
//      cout<<x<<'\n';
        qq.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].c+h[x]-h[v];
//          cout<<v<<' '<<e[i].c<<' '<<h[v]<<'\n';
            if(e[i].w&&dis[v]>dis[x]+w){
//              cout<<"aowufbh";
                dis[v]=dis[x]+w;
                fr[v].nxt=i;
                fr[v].to=x;
                if(!vis[v]) qq.push({dis[v],v});
            }
        }
//      cout<<'\n';
    }
    return dis[t]!=1e18;
}
void PD(){
    spfa();
//  for(int i=1;i<=n;i++) cout<<h[i]<<' ';
//  cout<<"\n\n";
    while(dij()){
        int minn=1e18;
        for(int i=1;i<=n;i++){
//          cout<<dis[i]<<' ';
            h[i]+=dis[i];
        }
//      cout<<'\n';
        for(int i=t;i!=s;i=fr[i].to){
            minn=min(minn,e[fr[i].nxt].w);
        }
//      cout<<minn<<'\n';
        for(int i=t;i!=s;i=fr[i].to){
            e[fr[i].nxt].w-=minn;
            e[fr[i].nxt^1].w+=minn;
        }
        answ+=minn;
        ansc+=minn*h[t];
    }
}
string main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w,c;
        cin>>u>>v>>w>>c;
        add(u,v,w,c); 
    }
    PD();
    cout<<answ<<' '<<ansc<<'\n';
    return "Primal-Dual 原始对偶算法长得真好看啊！\n";
}
}
namespace kong{bool ed;double kj(){return (&st-&ed)/1048576.0;}}
signed main(){
    cerr<<zhu::main()<<'\n'<<kong::kj();
    return 0;
}

多路增广

这个通常快得多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace kong{bool st;}
namespace zhu{
int tot=1,head[1001000],answ,ansc,n,m,s,t,h[1001000],dis[1001000],vis[1001000],cur[1001000];
queue<int> q;
struct node{
    int v,id;
    bool operator<(const node& a)const{
        return v>a.v;
    }
};
priority_queue<node> qq;
struct{
    int nxt,to,w,c;
}e[2002000];
//fr 记录找到的增广路
void add(int u,int v,int w,int c){
    e[++tot]={head[u],v,w,c};
    head[u]=tot;
    e[++tot]={head[v],u,0,-c};
    head[v]=tot;
    return;
}
void spfa(){
    while(!q.empty()) q.pop();
    memset(vis,0,sizeof vis);
    memset(h,0x3f,sizeof h);
    h[s]=0;vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to,c=e[i].c;
            if(e[i].w&&h[v]>h[x]+c){
                h[v]=h[x]+c;
                if(vis[v]) continue;
                vis[v]=1;
                q.push(v);
            }
        }
    }
}
bool dij(){
    while(!qq.empty()) qq.pop();
    for(int i=1;i<=n;i++) vis[i]=0,dis[i]=1e18;
    dis[s]=0;
    qq.push({0,s});
    while(!qq.empty()){
        int x=qq.top().id;
        qq.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].c+h[x]-h[v];
            if(e[i].w&&dis[v]>dis[x]+w){
                dis[v]=dis[x]+w;
                if(!vis[v]) qq.push({dis[v],v});
            }
        }
    }
    for(int i=1;i<=n;i++) vis[i]=0;
    return dis[t]!=1e18;
}
int dfs(int x,int flow){
    if(x==t) return flow;
    int sum=0;
    vis[x]=1;
    for(int i=cur[x];i;i=e[i].nxt){
        cur[x]=i;
        int v=e[i].to;
        if(e[i].w&&!vis[v]&&h[v]==h[x]+e[i].c){
            int ff=dfs(v,min(flow,e[i].w));
            e[i].w-=ff;
            e[i^1].w+=ff;
            sum+=ff;
            flow-=ff;
            ansc+=ff*e[i].c;
            if(!flow) break;
        }
    }
    vis[x]=0;
    return sum;
}
void PD(){
    spfa();
//  for(int i=1;i<=n;i++) cout<<h[i]<<' ';
//  cout<<"\n\n";
    while(dij()){
        for(int i=0;i<=n+m;i++){
            h[i]+=dis[i];
            cur[i]=head[i];
        }
        int k=dfs(s,1e9);
        answ+=k;
//      cerr<<k<<'\n';
    }
}
string main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w,c;
        cin>>u>>v>>w>>c;
        add(u,v,w,c); 
    }
    PD();
    cout<<answ<<' '<<ansc<<'\n';
    return "Primal-Dual 原始对偶算法长得真好看啊！\n";
}
}
namespace kong{bool ed;double kj(){return (&st-&ed)/1048576.0;}}
signed main(){
    cerr<<zhu::main()<<'\n'<<kong::kj();
    return 0;
}

顺此一提，这个算法的缺点是无法动态加点