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

海洋守卫者 · 2025-04-08 16:39:54 · 题解

P3381 【模板】最小费用最大流

解题思路

最小费用最大流问题在本质上就是在最大流问题的前提下给边加上费用，并求流量最大时费用的最小值。

根据费用的性质，很容易联想到路径长度。以费用作为路径的长度，每次都沿着最短路进行增广，并累加本次增广的总费用，修改剩余的流量，不断重复，直到流量 flow\le 0 时退出。（本质上与 Dinic 没有太大差别，仅是增加了一个最短路）

实现细节

• 对于任意一条容量为 w 费用为 c 的边，应当创建一条对应的反向边，容量初始为 0，费用为 -w。
• 由于负权边的存在，这里使用最短路算法为 SPFA；如果使用 Dijkstra 来求解费用流，则须要对网络进行一些处理，这里不再赘述，感兴趣可以看这篇博客。

完整代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN=5e4+5,oo=0x3f3f3f3f;
int n,m,s,t,h[MAXN],ec=1,ans,sum;
struct Edge{
    int u,v,w,c,nxt;
}e[MAXN<<2];
inline void AddEdge(int u,int v,int w,int c)
{
    e[++ec]={u,v,w,c,h[u]};
    h[u]=ec;
}
inline void Add(int u,int v,int w,int c)
{
    AddEdge(u,v,w,c);
    AddEdge(v,u,0,-c);
}
int vis[MAXN],dis[MAXN];
queue<int>que;
bool SPFA(int s,int t){ 
    while(!que.empty())que.pop();
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    vis[t]=1,que.push(t),dis[t]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        vis[u]=0;
        for(int i=h[u];i;i=e[i].nxt){
            if(e[i^1].w&&dis[u]+e[i^1].c<dis[e[i].v]){
                dis[e[i].v]=dis[u]+e[i^1].c;
                if(vis[e[i].v])continue;
                que.push(e[i].v);
                vis[e[i].v]=1;
            }
        }
    }
    return dis[s]!=oo;
} 
int DFS(int u, int t, int f){ 
    if(u==t||!f)return f;
    vis[u]=1;
    int rest=f;
    for(int i=h[u];i;i=e[i].nxt){
        if(dis[e[i].v]!=dis[u]-e[i].c||!e[i].w||vis[e[i].v])continue;
        int tmp=DFS(e[i].v,t,min(e[i].w,rest));
        if(!tmp){
            dis[e[i].v]=oo;
            continue;
        }
        e[i].w-=tmp;
        e[i^1].w+=tmp;
        rest-=tmp;
        if(!rest)return f;
    }
    vis[u]=0;
    return f-rest;
}
void Slove(int s,int t){ 
    ans=sum=0;
    while(SPFA(s,t)){
        memset(vis,0,sizeof vis);
        int tmp=DFS(s,t,oo);
        ans+=tmp;sum+=tmp*dis[s];
    }
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=1,u,v,w,c;i<=m;i++)
    {
        scanf("%d %d %d %d",&u,&v,&w,&c);
        Add(u,v,w,c);
    }
    Slove(s,t);
    printf("%d %d",ans,sum);
    return 0;
}