本文共 2423 字，大约阅读时间需要 8 分钟。
我们现在来考虑比一般的网络流复杂一点的一个模型：最小费用最大流（Minimum Cost Maximum Flow，MCMF）。
现在网络上的每条边，除了容量外，还有一个属性：单位费用。一条边上的费用等于流量×单位费用。我们知道，网络最大流往往可以用多种不同的方式达到，所以现在要求：在保持流最大的同时，找到总费用最少的一种。
如下图，有多种方式可以达到最大流3，但是S->3->T (2) + S->3->2->T (1)这种流法的费用是7×2+5×1=19，而S->3->T (2) + S->1->2->T (1)这种流法的费用则是7×2+4×1=18，后者比前者的费用更低。事实上，后者正是这个网络的最小费用最大流。
其实这个问题很好解决。我们已经知道，只要建了反向边，无论增广的顺序是怎样，都能求出最大流。所以我们只需要每次都增广费用最少的一条路径即可。具体地，把EK算法里的BFS换成SPFA：
int head[MAXN], cnt = 1; // 这里特意把存图也贴出来，记住额外存一个参数c（费用）struct Edge{ int to, w, c, next;} edges[MAXM * 2];inline void add(int from, int to, int w, int c){ edges[++cnt].to = to; edges[cnt].w = w; edges[cnt].c = c; edges[cnt].next = head[from]; head[from] = cnt;}int n, m, s, t, last[MAXN], flow[MAXN], inq[MAXN], dis[MAXN];queue Q;bool SPFA(){ while (!Q.empty()) Q.pop(); memset(last, -1, sizeof(last)); memset(inq, 0, sizeof(inq)); memset(dis, 127, sizeof(dis)); flow[s] = INF; dis[s] = 0; Q.push(s); while (!Q.empty()) { int p = Q.front(); Q.pop(); inq[p] = 0; for (int eg = head[p]; eg != 0; eg = edges[eg].next) { int to = edges[eg].to, vol = edges[eg].w; if (vol > 0 && dis[to] > dis[p] + edges[eg].c) // 容量大于0才增广 { last[to] = eg; // 记录上一条边 flow[to] = min(flow[p], vol); // 更新下一个点的流量 dis[to] = dis[p] + edges[eg].c; // 注意这里是c不是w if (!inq[to]) { Q.push(to); inq[to] = 1; } } } } return last[t] != -1;}int maxflow, mincost;inline void MCMF() // 这里要求两个值，直接改成给全局变量赋值了，传pair也可以吧{ while (SPFA()) { maxflow += flow[t]; mincost += dis[t] * flow[t]; for (int i = t; i != s; i = edges[last[i] ^ 1].to) { edges[last[i]].w -= flow[t]; edges[last[i] ^ 1].w += flow[t]; } }} 注意：建边的时候要这样建：
add(x, y, v, c);add(y, x, 0, -c);
反向边的费用是正向边的相反数（只要你知道建反向边的目的，这应该是显然的）。
你会发现，其实这和一般的EK算法没多大区别（毕竟SPFA可以看作一种特殊的BFS）。网上好多文章先说“MCMF就是把dinic的BFS换成SPFA”，然后拍上来的代码明明就是把EK的BFS换成SPFA……我都怀疑他们是互相抄的（划掉）。其实如果是一般的dinic的话，在这个问题上并没有什么优势啊，毕竟多路增广和当前弧优化好像在MCMF问题上作用都不大？当然，经过某些特别的优化，应该还是能取得一些优势吧。
至于为什么用SPFA而不是Dij，主要是因为很多费用流模型都会涉及到负权边（包括洛谷模板题）。众所周知，SPFA的复杂度不稳定，不过，这个算法的复杂度本身就不稳定，还与流量有关，所以一般不用担心被卡。当然，经过特殊处理，还是可以跑Dij的，暂且不讲。
Pecco：算法学习笔记（目录）zhuanlan.zhihu.com
转载地址：https://blog.csdn.net/weixin_39926014/article/details/111017053 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
