最小费用最大流问题

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从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]