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

fengzhaoyu · 2025-07-10 20:11:53 · 题解

~~原始对偶算法是个好东西~~

思路

前置芝士：dinic-算法。

看看题解没有 dijkstra 加 dinic 的，这里来写一下。

首先要知道，网络流就是对于一条 u\rightarrow v 的路径反向再建权值为 0 的路径，如果这条路经过了 x 的流量，那么他的反边就会增加 x 的权值，以便以后可以“反悔”。最小费用最大流是贪心地每次按价格的最短路进行增广，那很容易想到加一个 spfa，每次都找一条 s\rightarrow t 的最短路进行增广，直到不存在这样的路径为止。可以证明，此时的路径一定最优（蒟蒻太蒟蒻了，不会证，有意愿者可以上网查证明方法），详见代码。

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=5e4+15,M=5e5+15,inf=INT_MAX;
int read()
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}
int cur[N],to[M],ne[M],f[M],w[M],d[N],vis[N];
int dis[N],hh[N];
int n,m,s,t,idx;
void add(int u,int v,int ww,int c)
{
    to[idx]=v;
    ne[idx]=hh[u];
    f[idx]=ww;// 流量限制
    w[idx]=c;// 价格
    hh[u]=idx++;
}
bool spfa()//求最短路并判断此时是否存在增广路
{
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;i++) dis[i]=inf;
    queue<int>q;
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    d[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            if(f[i]&&dis[v]>dis[u]+w[i])
            {
                dis[v]=dis[u]+w[i];
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[t]<inf) return 1;
    return 0;
}
int ans1=0,ans2=0;
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    vis[u]=1;//这样是为了下文判断是否存在负环，如果有，可直接跳过
    for(int i=cur[u];i!=-1;i=ne[i])
    {
        cur[u]=i;//当前弧优化
        int v=to[i];
        if(f[i]&&dis[v]==dis[u]+w[i]&&vis[v]==0)//保证了一定会按最短路增广
        {
            int ff=dfs(v,min(mf,f[i]));
            f[i]-=ff;
            f[i^1]+=ff;
            sum+=ff;
            mf-=ff;
            ans2+=ff*w[i];//由于dinic是多路增广，所以只能边遍历便更新值
            if(mf==0) break;
        }
    }
    vis[u]=0;
//  if(sum==0) d[u]=0;
    return sum;
}
void Dinic()
{
    while(spfa())
    {
        memcpy(cur,hh,sizeof hh);
        ans1+=dfs(s,inf);
    }
    printf("%d %d\n",ans1,ans2);
}
int main()
{
    memset(hh,-1,sizeof hh);
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read(),c=read();
        add(u,v,w,c);
        add(v,u,0,-c);
    }
    Dinic();
    return 0;
}

但是，我们知道，关于 spfa，它~~已经死了~~远不如 dijkstra，那有没有一种方法使此题能用 dijkstra 呢？有，原始对偶算法。我们先想，此题本来不用 dijkstra 的原因是因为有负环，那我们是否能变负为正呢？

引入势函数（对偶变量）h_{u}，为每个节点 v 维护一个势能值。
重新定义边权：对每条边 u\rightarrow v，定义修正边权：c'_{u,v}=c_{u,v}+h_u−h_v。
其中 c_{u,v} 是原始费用。可以通过设置合适的 h_u，使得所有修正权 c'_{u,v}\geq 0，从而允许使用 dijkstra 算法。
那么由此可得：c_{u,v}+h_u-h_v\geq 0，将 h_v 移项——不就是最短路中的松弛操作吗？那好，初始势函数的值可以用从 s 出发的最短路来表示。(正确性的证明：对于一条增广路，一条边 c'_{i,j}=c_{i,j}+h_i-h_j，它的下一条边 c'_{j,k}=c_{j,k}+h_j-h_k，当它们相加时，h_j 抵消了！由此推出：\sum c'_{u,v}=\sum c_{u,v}+h_s-h_t，因此，路径的实际费用与修正费用仅相差一个常数，与路径无关。也就是说，每次增广多带来的值是一样的。)
设 d{v} 是当前残量网络中从 s 到 v 的最短修正距离（dijkstra 得），势函数更新为 $h{newv}=h{oldv}+d{v}。此时是否仍然保持非负性？对于一条边，dv\leq d{u}+c'_{u,v}=du+c{u,v}+h{oldu}-h{oldv}，整理得：c{u,v}+h{oldu}+du-h{oldv}+dv\geq 0，其中 h{oldu}+du-h{oldv}$ 就是势函数更新了。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int N=1e5+15,inf=INT_MAX;
int read()
{
    int t=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}
int cur[N],to[N],ne[N],f[N],w[N],vis[N];
int dis[N],h[N],hh[N];
int n,m,s,t,idx;
void add(int u,int v,int ww,int c)
{
    to[idx]=v;
    ne[idx]=hh[u];
    f[idx]=ww;
    w[idx]=c;
    hh[u]=idx++;
}
void spfa()//求h初始值，因为只跑一次，所以不会慢
{
    memset(h,0x3f,sizeof h);
    queue<int>q;
    q.push(s);
    vis[s]=1;
    h[s]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            if(f[i]&&h[v]>h[u]+w[i])
            {
                h[v]=h[u]+w[i];
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }

}
bool dijkstra()
{
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;i++) dis[i]=inf;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    q.push({0,s});
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=hh[u];i!=-1;i=ne[i])
        {
            int v=to[i];
            if(f[i]&&dis[v]>dis[u]+w[i]+h[u]-h[v])
            {

                dis[v]=dis[u]+w[i]+h[u]-h[v];
                q.push({dis[v],v});
            }
        }
    }
    return dis[t]!=inf;
}
int ans1=0,ans2=0;
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    vis[u]=1;
    for(int i=cur[u];i!=-1;i=ne[i])
    {
        cur[u]=i;
        int v=to[i];
        if(f[i]&&vis[v]==0&&h[v]==h[u]+w[i])
        {

//          cout<<"ll";
            int ff=dfs(v,min(mf,f[i]));
            f[i]-=ff;
            f[i^1]+=ff;
            sum+=ff;
            mf-=ff;
            ans2+=ff*w[i];
            if(mf==0) break;
        }
    }
    vis[u]=0;
    return sum;
}
void Dinic()
{
    spfa();
    while(dijkstra())
    {
        memset(vis,0,sizeof vis);
        memcpy(cur,hh,sizeof hh);
        for(int i=1;i<=n;i++) h[i]+=dis[i];
        int k=dfs(s,inf);
        ans1+=k;
    }
    printf("%d %d\n",ans1,ans2);
}
int main()
{
    memset(hh,-1,sizeof hh);
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read(),c=read();
        add(u,v,w,c);
        add(v,u,0,-c);
    }
    Dinic();
    return 0;
}

~~完美撒花！~~