费用流

参考资料

• 费用流 - OI Wiki

简介

最小费用最大流（MCMF）在最大流的基础上，要求在流量达到最大的前提下使总费用最小，每条边带有容量与单位流量费用两个属性。

常用 SSP（连续最短路）算法：把最大流中「BFS 找任意增广路」换成「以单位费用为边权找最短的增广路」，每次沿费用最短的增广路增广。找最短路可用 SPFA（允许负费用边）或配合势能的 Dijkstra。

例题

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

给定一张带容量与单位费用的有向图及源点 $s$、汇点 $t$，求在 $s$ 到 $t$ 流量最大的前提下，所有可行方案中的最小总费用。