最小成本最大流（min-cost max-flow）

樸素最大流只問你能運多少。但每根管子往往還有每單位的運價，而在所有能運出最大量的方法中，你想要最便宜的那個。或者你固定一個要運的目標量，把它的成本最小化。最小成本最大流恰好回答這點：盡量推送最多的流，而在所有最大流中，找一個總成本最小的。

設定在每條邊上、與其容量並列，加一個每單位流量的成本 a(u, v)。流 f 的成本是對各邊的 a(u, v) * f(u, v) 求和，目標是一個使此和最小的最大值流（或一個給定目標值、成本最小的流）。關鍵工具是逐次最短路徑法：反覆在殘餘網路中找一條成本最小（最便宜，而非邊數最短）的增廣路徑並沿之推送。殘餘網路也必須帶成本——一條後向殘餘邊的成本是 減 a(u, v)，因為撤銷流量會退回它的價錢。由於邊成本可能為負（那些後向邊），你用貝爾曼-福特找最便宜的增廣路徑，或在做位勢重新賦權（Johnson 技巧）使所有縮減成本非負後改用戴克斯特拉。一個乾淨的不變量讓它正確：若你總是沿最便宜的路徑增廣，流對其當前的值始終是最小成本流，故最終的最大流也是最小成本的。

最小成本最大流是「帶成本的指派」問題的主力：指派問題（把工人配到工作以最小化總成本）、運輸與物流，以及許多既要最大吞吐又在乎價錢的排程問題。它同時推廣了最短路徑（單一最便宜的流量單位）與最大流（忽略成本）。誠實的提醒：它比樸素最大流更重——逐次最短路徑大致以 O(V * E * f) 執行，或用位勢以每單位值風格的 O(f * (E + V log V)) 為界，故極大的流值會吃虧——而你必須用一個能容忍負成本後向邊的方法，這正是為何單用樸素戴克斯特拉不夠。