最小費用最大流問題

最小費用最大流問題是經濟學和管理學中的一類典型問題。在一個網絡中每段路徑都有「容量」和「費用」兩個限制的條件下，此類問題的研究試圖尋找出：流量從A到B，如何選擇路徑、分配經過路徑的流量，可以達到所用的費用最小的要求。

問題提出

有足夠多輛卡車要將數量無限的某種物品從一個地點運輸到另外一個地點，現在有有限條單向行駛道路直接或者間接地連接了這兩地。但是每一條道路都有運輸通過總數量的限制，稱為容量，同時攜帶物品通過該路段時，都會按照攜帶物品數量多少被收取一定的費用。如何合理地安排每輛車的行駛路線，使得在運輸的貨物總量儘可能大的情況下，交付的總費用儘可能少？

注意，在此問題中總費用僅包括攜帶物品通過路段時被收取的費用，車輛和路線安排上沒有限制，但通過某一路段的物品數量總和不得超過它的容量，收取的費用與攜帶物品的多少成正比。

定義

最小費用最大流建立在最大流和網絡流問題的基礎之上。

帶權有向圖 $G=(V,E)$ 是一個特殊的容量網絡,所有邊 $(u,v)\in E$ 包含 $c(u,v)\in \mathbb {R} ^{+}$ , 稱為這條弧的容量；以及 $w(u,v)\in \mathbb {R}$ 稱為這條邊的費用。

容量網絡中一個可行流的總費用為 $\sum \left(f(u,v)\times w(u,v)\right)$ . 所有最大流中總費用最少的稱為這個容量網絡的最小費用最大流。

思想

求解最小費用最大流可以採用貪心的思想，即每一次找一條從源點到匯點的增廣路，同時保證這條增廣路是目前所有增廣路中運輸單位物品費用最小的。由於對於一個確定的容量網絡，它的最大流是有限且確定的，所以一定存在某一時刻無法再在當前殘量網絡中找到增廣路，這時算法結束，總流量等於最大流，而又由於每一次增廣的單位花費都是最小的，所以總花費也必定是所有方案中最少的。

可見，求解這類問題的關鍵是每一次找到一條目前所有增廣路中運輸單位物品費用最小的增廣路。如果將費用看作兩點之間的距離，那麼這就轉換為了一個最短路問題。

求解方法

利用隊列優化的Bellman-Ford算法求解

在最短路問題中，我們利用隊列優化的Bellman-Ford算法（以下簡稱 SPFA) 求單源最短路，進而得到兩個結點之間的最短路徑 $dis_{u\to v}$ . 使用類似的思想，將兩點之間的距離轉換為兩點之間的費用，然後運行 SPFA 算法，同時維護可以從源點到達每個點的最大流量，得到從源點到匯點一條費用最小的增廣路，使用這條路徑進行增廣，然後重複這個過程。直到找不到增廣路，此時的總流量和總費用即為所求答案。

具體而言，記源點為 $s$ ,匯點為 $t$ . 設 $u\in V,\ d(u)$ 代表從 $s$ 到 $u$ 每單位流量花費的最小費用， $f(u)$ 代表使用上述每單位流量花費費用最小的路徑能夠讓多少流量從源點流到 $u$ . 在 SPFA 每一輪循環過程中，從隊列中取出一個結點 $u$ , 並枚舉每一條邊 $(u,v)\in E$ , 如果滿足 $d(v)>d(u)+w(u,v)$ 則更新相應的 $d(v)=d(u)+w(u,v)$ 和 $f(v)=\min\{f(u),f(u,v)\}$ ，同時記錄 $last(v)$ 代表來到結點 $v$ 使用了哪一條弧. 求出單源最短路後，就等同於找到了一條增廣路，花費 $f(t)\times d(t)$ 將流量增大 $f(t)$ . 增廣結束後，我們需要更新這條增廣路上弧和反向弧的流量。^[1]

需要注意的是，與求解單源最短路問題時類似，雖然SPFA能夠處理帶有負權的邊（也就是費用為負的弧），但是如果出現了負環，則會讓算法陷入死循環。

實際應用與推廣

利用這種算法，不僅可以解決前面提到的類似問題，經過變換也可以通過建立相應模型間接地解決許多問題。

二分圖的帶權匹配

二分圖的最佳帶權匹配問題在經過變形之後，可以使用最小費用最大流相關算法進行求解。首先對於二分圖中的每一條邊，視其容量為1，它的權值也就是費用，由於最佳帶權匹配需要所有匹配邊權值之和最大，所以視其費用為權值的相反數。正確地求得最小費用 $C$ 之後，最佳帶權匹配的總權值之和 $T$ 就是最小費用的相反數 $T=-C$ .

需要注意的是，二分圖匹配問題中有許多個源點和許多個匯點，一條可行流可以從其中任何一個源點出發到達任何一個匯點結束，對於這種情況，我們可以建立一個額外的源點何一個額外的匯點，將額外源點與所有源點連容量為 $\infty$ 費用為 $0$ 的弧，額外匯點也執行類似的操作。完成這一步後，所得到的模型已與普通最小費用最大流無異。

參考程序

C++

#include<bits/stdc++.h>

constexpr auto MAXN = 5000 + 50;

struct Edge {
	int fr, to, residual, cost;
};
std::vector<Edge>edges; std::vector<int> G[MAXN];
int s, t, maxFlow, minCost;
int last[MAXN], flow[MAXN], dis[MAXN];
bool inQueue[MAXN];

bool SPFA() {
	memset(inQueue, false, sizeof(inQueue)); std::fill(dis, dis + MAXN, INT_MAX);
	std::queue<int> que; que.push(s); inQueue[s] = true; 
	flow[s] = INT_MAX; last[s] = 0; dis[s] = 0;

	int nowAt;
	while (!que.empty()) {
		nowAt = que.front(); que.pop(); inQueue[nowAt] = false;
		for (int i = 0; i < G[nowAt].size(); i++) {
			Edge& it = edges[G[nowAt][i]];
			if (it.residual > 0 && dis[it.to] > dis[nowAt] + it.cost) {
				dis[it.to] = dis[nowAt] + it.cost;
				last[it.to] = G[nowAt][i];
				flow[it.to] = std::min(flow[nowAt], it.residual);
				if (!inQueue[it.to]) { inQueue[it.to] = true; que.push(it.to); }
			}
		}
	}
	if (dis[t] == INT_MAX)return false;

	maxFlow += flow[t]; minCost += dis[t] * flow[t];
	nowAt = t;
	while (nowAt != s) {
		edges[last[nowAt]].residual -= flow[t];
		edges[last[nowAt] ^ 1].residual += flow[t];
		nowAt = edges[last[nowAt]].fr;
	}
    return true;
}

void MCMF() {
	maxFlow = 0; minCost = 0;
	while (SPFA());
}

signed main()
{
	int fr, to, cost, flow;
	int totNode, totEdges;

	scanf("%d%d%d%d", &totNode, &totEdges, &s, &t);
	for (int i = 0; i < totEdges; i++) {
		scanf("%d%d%d%d", &fr, &to, &flow, &cost);
		G[fr].push_back(edges.size()); edges.push_back({ fr,to,flow,cost });
		G[to].push_back(edges.size()); edges.push_back({ to,fr,0,-cost });
	}
    MCMF();

	printf("%d %d\n", maxFlow, minCost);

	//system("pause");
	return 0;
}

參見

參考文獻

^ 劉汝佳; 陳鋒. 朱英彪 , 編. Suan fa jing sai ru men jing dian xun lian zhi nan. Qing hua ta xue chu ban she. : 362. ISBN 978-7-302-29107-7.

[1] 劉汝佳; 陳鋒. 朱英彪 , 編. Suan fa jing sai ru men jing dian xun lian zhi nan. Qing hua ta xue chu ban she. : 362. ISBN 978-7-302-29107-7.

[1]