在打 P3705 [SDOI2017]新生舞会 时发现原代码似乎出了点问题。现在不推荐本博客的写法，更推荐类似于 Dinic 的 spfa+dfs 的写法，详见最下方的“附加代码”部分。

MCMF（基于 spfa 实现）

模板题：Luogu3381。

即给定一张网络，每条边都有一个权值和流量限度，这条边上每有一个流量，总费用就加上这个权值，你需要在保证总流量最大的前提下，使总费用最小。

考虑采用暴力最大流的方法，每次拓展一条线路。为保证总费用最小，这条线路应采用最短路算法，每次拓展的线路都是当前所有的线路中的最短路（边权就是该边的费用）。然后我们再每次遍历这条线路，令正边减去流量，反边加上流量即可。一直重复上述操作直至找不到新线路即可。

由于题目存在负权边，用 Dijkstra 处理比较麻烦（可以处理，详见模板题的其他题解），因此可以简单地使用 spfa 跑最短路。

下面给出代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
const int M=1e5+5;
int n,m,s,t;
struct node{
    int to,nxt,w,flow;
}e[M];
int cnt=1,head[N];
inline void add(int u,int v,int flow,int w){
    e[++cnt].to=v;e[cnt].nxt=head[u];
    e[cnt].w=w;e[cnt].flow=flow;
    head[u]=cnt;
}
int dis[N],vis[N],infl[N],pre[N];
queue<int> q;
inline bool spfa(){
    for(int i=1;i<=n;i++) dis[i]=2e9;
    memset(vis,0,sizeof(vis));
    q.push(s);dis[s]=0;vis[s]=1;infl[s]=1<<30;
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            if(!e[i].flow) continue;//没流量的边不考虑
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                pre[v]=i;infl[v]=min(infl[u],e[i].flow);//更新线路和流量
                if(!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    if(dis[t]==2e9) return 0;
    return 1;
}
int ans1,ans2;
inline void MCMF(){
    while(spfa()){//每次 spfa 拓宽
        int u=t;
        ans1+=infl[t];ans2+=infl[t]*dis[t];
        while(u!=s){//处理反悔
            int i=pre[u];
            e[i].flow-=infl[t];
            e[i^1].flow+=infl[t];
            u=e[i^1].to;
        }
    }
    printf("%d %d\n",ans1,ans2);
}
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);add(v,u,0,-c);//反边权值也是反的
    }
    MCMF();
    return 0;
}

例题

Luogu4015 运输问题 非常板的一道题。

Luogu1251 餐巾计划问题 相对有难度的 MCMF 题。

附加代码

本代码是 P3705 [SDOI2017]新生舞会 的部分代码，为最大费用最大流。

bool vis[N];
int mark[N];
double dis[N];
queue<int> q;
bool spfa() {
    for(int i=1;i<=t;i++) dis[i]=-1e9; 
    memset(vis,0,sizeof(vis));q.push(s);dis[s]=0;vis[s]=1;
    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;
            if(dis[v]<dis[u]+e[i].w&&e[i].flow){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]) q.push(v),vis[v]=1; 
            }   
        }
    }
    return dis[t]!=-1e9 ;
}
double Ans;
int dfs(int u,int in){
    mark[u]=1; 
    if(u==t) return in; 
    int out=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to; 
        if(!mark[v]&&dis[v]==dis[u]+e[i].w&&e[i].flow) {
            int tmp=dfs(v,min(in,e[i].flow)); 
            if(tmp){
                e[i].flow-=tmp,e[i^1].flow+=tmp;
                out+=tmp;in-=tmp;
                Ans+=tmp*e[i].w; 
                if(!in) return out; 
            }
        }
    }
    return out;
}
void MCMF() {
    Ans=0;
    while(spfa()) {
        mark[t]=1; 
        while(mark[t]){
            memset(mark,0,sizeof(mark));
            dfs(s,1e9);
        }
    }
}