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

· · 题解

更好的阅读体验

这是一道模板题。在做这道题之前，你应该要学会：

对此，我们以求解最大流的 Edmonds-Karp 算法为基础。EK 的过程是，每次选择一条 S \to T 的非满流路径并将其流满，称作一次增广，增广的路径称作增广路。

在求解最小费用的过程中，我们以 c(u, v) 为边权，每次选择 S \to T 的最短非满流简单路径作为增广路，这样就能求出最大流当中的最小费用。这就是 EK 求最大流的方法。

我们想想这个东西为什么是对的。

EK 结束的条件是图中不存在合法路径。一方面，根据最大流最小割定理，一个流是最大流当且仅当途中不存在增广路径。所以求出最大流的正确性显然。

另一方面，我们需要说明这种方案所需要的费用是最少的。记处于一个局面时的最小费用为 C_0，我们通过最短路进行一次增广后的最小费用为 C_1，此时假设我们存在另外一条增广路径求出的费用为 C_2 且 C_2 < C_1。由于 C_1 时当前局面下的的最短简单路径，因此 C_2 的增广路必然存在负环，和增广路的简单性相违背。

综上所述，我们证明了该算法的正确性。

我们回到实现上。我们可以使用 SPFA 算法寻找最短简单路径，在松弛的时候记录每个点的前驱。随后我们沿着记录的路径进行增广，同时将最小费用加上路径的边权和。

由于一次增广至少使最大流增加 1，假设原图最大流为 f，因此最多经过 f 轮增广后得出答案。由于使用的是 SPFA，因此一次增广的复杂度为 O(nm)，总复杂度是 O(nmf)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 5006
#define M 50006
using namespace std;
int n,m;
struct MCMF_Graph{//by dyc2022
int head[N],tot=2,s,t;
int dis[N],incf[N],pre[N],vis[N],maxflow,mincost;
struct Node{int nxt,to,w,c;}E[M<<1];
void addedge(int u,int v,int w,int c){E[tot]={head[u],v,w,c},head[u]=tot++;}
void addflow(int u,int v,int w,int c){addedge(u,v,w,c),addedge(v,u,0,-c);}
int SPFA()
{
    for(int i=1;i<=n;i++)dis[i]=1e15;
    queue<int> q;
    q.push(s),dis[s]=0,incf[s]=1e15,incf[t]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=E[i].nxt)
        {
            int v=E[i].to,w=E[i].w,c=E[i].c;
            if(!w||dis[v]<=dis[u]+c)continue;
            dis[v]=dis[u]+c,incf[v]=min(incf[u],w),pre[v]=i;
            if(!vis[v])q.push(v),vis[v]=1;
        }
    }
    return incf[t];
}
void EK()
{
    maxflow+=incf[t];
    for(int u=t;u!=s;u=E[pre[u]^1].to)
    {
        E[pre[u]].w-=incf[t],E[pre[u]^1].w+=incf[t];
        mincost+=incf[t]*E[pre[u]].c;
    }
}
void getflow(){while(SPFA())EK();}}G;
main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&G.s,&G.t);
    for(int i=1,u,v,w,c;i<=m;i++)
        scanf("%lld%lld%lld%lld",&u,&v,&w,&c),G.addflow(u,v,w,c);
    G.getflow();
    printf("%lld %lld\n",G.maxflow,G.mincost);
    return 0;
}