最大费用最大流：从概念到实现，解决收益最大化问题

1. 从“最小”到“最大”费用流问题的另一面一提到网络流里的费用流很多人脑子里蹦出来的第一个词就是“最小费用最大流”。这太正常了毕竟在大多数实际问题里我们追求的都是成本最小化用最少的钱把最多的货物从工厂运到市场用最短的路径把数据包从源头发到目的地用最低的能耗完成生产任务。教科书、算法竞赛、工程实现到处都充斥着“最小费用”的身影相关的算法比如最经典的基于SPFA或Dijkstra的连续最短路增广算法Successive Shortest Path, SSP以及更高效的原始-对偶算法Primal-Dual也都是为“最小化”这个目标量身定制的。但今天我想和你聊聊这个问题的“另一面”最大费用最大流。乍一听这像是个“反常识”的优化目标——我们居然要最大化“费用”这在实际中意味着什么难道我们要故意多花钱吗其实不然。这里的“费用”是一个广义的概念它可以是利润、收益、满意度、或者任何我们想要最大化的正向指标。比如在一个物流网络中每条边有一个“单位运量利润”我们希望在流量达到最大的前提下让总利润最高又比如在一个任务分配图中每条匹配边有一个“匹配得分”我们希望完成尽可能多的匹配并且总分最高。所以最大费用最大流解决的是“在流量最大的前提下总收益最大化”的问题。很多人第一次遇到这个问题时会下意识地想“这还不简单把最小费用最大流算法里的‘最短路径’改成找‘最长路径’不就行了” 这个直觉方向是对的但魔鬼藏在细节里。直接把SPFA改成找最长路在含有负权边的图上这是费用流问题的常态因为反向边带有负费用会立刻遇到麻烦——正环。在寻找最长增广路时如果图中存在正权环即沿着环走一圈总费用会增加那么算法可能会在这个环上无限循环流量不增费用却可以无限增大这显然不是我们想要的“最大流”状态下的解。因此处理最大费用最大流核心就在于如何巧妙地规避或处理正环问题或者更聪明地将它转化为我们熟悉的最小费用问题。2. 核心转化策略符号反转与负权处理面对最大费用最大流最直接、最可靠、也是最常用的策略就是转化。我们利用一个简单的数学事实最大化一个函数等价于最小化该函数的相反数。也就是说如果我们把原始网络中每条边的单位费用c(e)取其相反数即令c(e) -c(e)那么在新的网络G上求最小费用最大流得到的最小费用值取反后就是原始网络G的最大费用值同时流量方案完全一致。这个转化听起来完美无缺但立刻引出了一个关键问题负权边。在转化后的网络G中所有原本正费用的边都变成了负权边。而经典的最小费用最大流算法如SSP要求初始网络中不存在负权环即所有环的费用和非负才能保证每次增广都是沿着当前残量网络中的最短路径进行并最终找到全局最优解。如果初始图就包含负权边那么初始的残量网络中就可能存在负权环直接运行SSP算法可能会导致错误。因此我们的任务变成了在一个含有负权边但无负权环的网络上求解最小费用最大流。这里有几种主流的处理思路我将逐一拆解其原理和实现细节。2.1 方法一预先使用SPFA计算初始势能这是处理负权边最经典的方法结合了Johnson全源最短路算法中的思想。其核心是为每个节点引入一个“势能”h(v)通过对所有边进行势能重标定使得重标定后的边权非负从而可以安全地使用更高效的Dijkstra算法进行增广。步骤拆解构造转化网络将原始网络G中每条边的费用c(e)取反得到c(e) -c(e)构建网络G。计算初始势能在G的残量网络上初始时就是原图以超级源点S为起点运行一次SPFABellman-Ford的队列优化算法求出到每个节点v的最短距离dist[v]。这个dist[v]就是我们需要的初始势能h(v)。为什么SPFA可以因为它能处理负权边只要图中不存在从源点可达的负权环。在我们的最大费用转化场景中原始图G是无负权环的否则最大费用可能无界取反后的G就是无正权环的等价于无负权环相对于c因此SPFA可以正确求出最短距离。注意这里有一个关键点。我们必须确保从源点S出发能到达所有节点吗在流网络中这通常是成立的因为源点需要向汇点输送流量。如果不成立比如有些节点与源汇均不连通我们可以添加一个虚拟的超级源点连接到所有节点边权为0先跑一遍SPFA计算势能。但在标准的最大流问题设定中我们通常只关心从S到T的流那些无法从S到达的节点不会参与增广其势能可以设为0或者通过一次以S为起点的SPFA无法到达的节点距离保持为INF在后续势能更新中这些节点也不会被用到。势能重标定与Dijkstra增广得到初始势能h[]后对于残量网络中的任意一条边(u-v)其重标定后的权值w(u, v)为w(u, v) c(u, v) h[u] - h[v]可以证明这样重标定后的边权w是非负的。因此在每次寻找增广路时我们可以使用Dijkstra算法在w的图上求从S到T的最短路径效率远高于SPFA。更新势能与迭代找到一条增广路并更新流量后残量网络会改变一些边容量减少反向边容量增加。我们需要更新势能h以适应新的残量网络。更新公式为h_new[v] h_old[v] dist[v]其中dist[v]是上一轮Dijkstra算法在重标定后的图上求出的从S到v的最短距离。这个更新保证了下一轮重标定后的边权依然非负从而可以继续使用Dijkstra。计算最终费用当无法再找到增广路时算法结束。此时得到的是转化网络G上的最小费用min_cost。原始网络G的最大费用max_cost即为-min_cost。实现要点与避坑指南SPFA的初始化在计算初始势能时通常将dist[S] 0其他节点dist[v] 0或一个很大的数如1e18。这里我推荐初始化为0。为什么呢因为我们最终关心的是边权的相对值。如果所有h[v]初始为0那么第一次重标定w c 0 - 0 c边权可能为负无法直接用Dijkstra。所以必须先跑SPFA。而如果dist初始为0SPFA会基于实际的负权边去松弛计算出真正的“最短距离”。如果初始为一个很大的数SPFA可能无法正确松弛所有节点特别是那些从S不可达的节点导致计算出的势能无效。负环检测虽然在理论条件下原始图无正环不应出现负环但在代码实现中在SPFA阶段加入负环检测是一个好习惯。如果SPFA发现负环说明原始问题的最大费用可能无界即存在正权环可以无限刷钱这通常意味着问题模型本身有误或输入数据有问题。Dijkstra的实现由于重标定后的边权w非负可以使用标准的基于优先队列的Dijkstra。注意我们需要的dist[v]是在重标定图上的距离用于更新势能和寻找路径。费用累加在增广时累加的费用应该是原始边的费用c(e)即转化前的费用我们想要最大化的那个而不是重标定后的费用w或转化后的费用c(e)。通常的做法是在增广路径上对于每条正向边累加流量 * c(e)对于每条反向边对应回退流量累加流量 * (-c(e))因为回退流量相当于抵消了之前的费用。2.2 方法二始终使用SPFA进行增广这是一个更“懒惰”但实现更简单的方法。既然转化后的网络含有负权边而我们又知道一个能处理负权边的单源最短路算法SPFA那为什么不一直用它呢步骤简述同样构建转化网络G费用c(e) -c(e)。在每次寻找增广路时都在当前的残量网络上运行SPFA算法寻找从S到T的最短路径在c意义下。沿该路径增广更新流量和残量网络。重复步骤2-3直到无法找到增广路。优缺点分析优点实现极其简单无需势能初始化、重标定、Dijkstra适配等复杂步骤。代码逻辑和最小费用最大流完全一致只是初始费用取反了。缺点效率较低。SPFA在最坏情况下的时间复杂度是O(VE)而Dijkstra是O((VE)logV)。对于边数较多、结构复杂的图SPFA可能会慢很多尤其是在算法竞赛中可能会有被卡的风险。适用场景适用于快速原型验证、问题规模较小节点和边数在几百级别、或者对运行时间不敏感的场合。在教学习和理解算法原理时这也是一个很好的起点。一个重要提醒即使使用SPFA也必须确保图中没有负权环在c意义下。在最大费用问题中这等价于原始图没有正权环。SPFA算法本身可以检测到负环如果在增广过程中发现从S出发有负环算法应终止并报告“费用无界”。2.3 方法三对偶变换与问题重构这是一种更“本质”的视角。我们不去动网络本身而是修改优化目标。标准的最小费用最大流问题是线性规划的一个特例。最大费用最大流是其对偶问题吗不完全是但我们可以通过定义一个“收益”变量来重构。设原始边(u, v)的容量为cap(u,v)单位费用为cost(u,v)我们想最大化它。我们定义flow(u,v)为实际流量。 目标函数Maximize Σ( flow(u,v) * cost(u,v) )约束条件流量守恒、容量限制、非负流量。如果我们令profit(u,v) cost(u,v)那么这就是一个标准的最大收益最大流问题。从线性规划的角度我们可以将目标函数乘以-1转化为最小化问题Minimize Σ( flow(u,v) * (-cost(u,v)) )这正好就是我们“取反费用”的数学解释。所以方法一和方法二本质上都是这种对偶/重构思想的具体算法实现。3. 算法模板实现与代码解析基于势能Dijkstra这里我给出一个基于C的、采用势能法即方法一的最大费用最大流实现模板。这个模板在竞赛和工程中都非常实用。#include bits/stdc.h using namespace std; typedef long long ll; const ll INF 1e18; const int MAXN 5005; // 根据题目调整节点数 const int MAXM 50005 * 2; // 注意边数要开两倍正向反向 struct Edge { int to, next; ll cap, cost; // 容量费用这里是原始费用即我们希望最大化的值 } e[MAXM]; int head[MAXN], tot; // 图初始化 inline void init() { tot 1; // 从1开始方便异或找反向边 memset(head, 0, sizeof(head)); } inline void addEdge(int u, int v, ll cap, ll cost) { e[tot] {v, head[u], cap, cost}; head[u] tot; e[tot] {u, head[v], 0, -cost}; // 反向边容量0费用为-cost head[v] tot; } ll dist[MAXN], h[MAXN]; // h为势能 int preV[MAXN], preE[MAXN]; // 前驱节点和前驱边用于回溯增广路 bool inq[MAXN]; // 使用SPFA计算初始势能返回false表示存在从S可达的负环即原图存在正环 bool spfa(int S, int T, int n) { fill(dist, dist n 1, INF); fill(inq, inq n 1, false); queueint q; dist[S] 0; q.push(S); inq[S] true; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (e[i].cap 0 dist[v] dist[u] e[i].cost) { // 注意这里用的是原始边的cost dist[v] dist[u] e[i].cost; preV[v] u; preE[v] i; if (!inq[v]) { q.push(v); inq[v] true; } } } } // 检查是否所有可达节点都完成了松弛这里简化处理通常dist[T] ! INF即表示有路 // 更严格的负环检测可以记录入队次数超过n次则认为有负环。 return dist[T] ! INF; } // 使用Dijkstra寻找增广路在势能重标定后的图上 bool dijkstra(int S, int T, int n) { fill(dist, dist n 1, INF); priority_queuepairll, int, vectorpairll, int, greater pq; // 最小堆 dist[S] 0; pq.emplace(0, S); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 旧的、无效的距离值 for (int i head[u]; i; i e[i].next) { int v e[i].to; // 关键边权重标定 w cost h[u] - h[v] ll w e[i].cost h[u] - h[v]; if (e[i].cap 0 dist[v] dist[u] w) { dist[v] dist[u] w; preV[v] u; preE[v] i; pq.emplace(dist[v], v); } } } return dist[T] ! INF; } // 主函数返回最大流 maxFlow 和最大费用 maxCost pairll, ll minCostMaxFlow(int S, int T, int n) { ll maxFlow 0, minCost 0; // 注意这里minCost是在转化后的网络G‘上的费用 // 第一步用SPFA计算初始势能 if (!spfa(S, T, n)) { // 如果一开始就没有增广路直接返回 return {0, 0}; } for (int i 1; i n; i) { h[i] dist[i]; // 初始势能就是SPFA算出的最短距离 } // 第二步使用势能Dijkstra进行增广 while (dijkstra(S, T, n)) { // 更新势能 for (int i 1; i n; i) { if (dist[i] INF) { // 只更新可达节点的势能 h[i] dist[i]; } } // 找到增广路径上的最小残量 ll flow INF; for (int v T; v ! S; v preV[v]) { int ei preE[v]; flow min(flow, e[ei].cap); } // 增广更新流量和残量网络 for (int v T; v ! S; v preV[v]) { int ei preE[v]; e[ei].cap - flow; e[ei ^ 1].cap flow; // 反向边增加容量 } maxFlow flow; // **注意**这里累加的费用是原始边的费用 * 流量 // dist[T] 是重标定图上的最短距离需要转换回原始费用 // 根据势能理论原始费用之和 (dist[T] h[T] - h[S]) * flow // 由于h[S]在第一次SPFA后通常为0且每次迭代h[S]保持不变dist[S]0h[T]是当前势能 // 更简单的做法直接累加路径上每条边的原始费用 // 这里我们采用公式计算避免回溯 minCost flow * (dist[T] h[T] - h[S]); // 这个结果是在转化网络G’上的费用是负数或零 } // minCost是转化网络上的最小费用是个负数或零 // 原始网络的最大费用就是 -minCost ll maxCost -minCost; return {maxFlow, maxCost}; } int main() { int n, m, S, T; cin n m S T; init(); for (int i 0; i m; i) { int u, v; ll cap, cost; cin u v cap cost; addEdge(u, v, cap, cost); // 输入的cost是原始费用即我们要最大化的值 } auto [flow, cost] minCostMaxFlow(S, T, n); cout flow cost endl; // 输出最大流和最大费用 return 0; }代码关键点解析与避坑费用存储在Edge结构体中cost字段存储的是原始费用即我们希望最大化的那个值。在addEdge中添加反向边时费用设置为-cost。这是所有计算的基础。势能初始化spfa函数这个函数非常重要。它运行在转化后的网络上吗仔细看它使用的是e[i].cost即原始费用。而我们之前说转化网络是c -c。这里为什么直接用原始费用因为SPFA在这里的目的不是找增广路而是计算一个初始势能h使得对于所有边(u,v)c h[u] - h[v] 0成立。如果我们把c替换为-c那么我们需要求的h要满足-c h[u] - h[v] 0即c h[v] - h[u] 0。这相当于在原始费用c的图上以T为源点求最长路或者符号反过来。两种理解是等价的但使用原始费用c进行SPFA计算出的dist[v]直接作为h[v]在后续dijkstra中我们使用w cost h[u] - h[v]作为重标定边权其正确性是可以证明的。这样实现更直观避免了在代码中显式地存储两份费用。Dijkstra中的边权重标定ll w e[i].cost h[u] - h[v];这是算法的核心。e[i].cost是原始费用h是势能。这行代码保证了w非负从而允许Dijkstra的正确运行。费用累加minCost flow * (dist[T] h[T] - h[S]);这是计算增广所带来费用变化的优雅方式。dist[T]是重标定图上的最短距离h[T]和h[S]是增广前的势能。可以证明dist[T] h[T] - h[S]恰好等于增广路径上所有边的原始费用之和。这样我们就不需要回溯路径去累加了。注意这里累加的是转化网络上的费用因为用的是原始费用但我们的目标是最小化-c的和所以这个minCost其实是负的。最终结果函数返回的minCost是转化网络上的总费用一个非正数。所以最大费用maxCost -minCost。关于负环/正环如果原始图存在正权环那么在SPFA阶段可能会因为存在c h[u] - h[v]始终无法满足非负即存在负环而导致SPFA无法收敛或计算出错。一个健壮的实现应该在SPFA中加入节点入队次数计数如果某个节点入队超过n次则判断存在负环此时最大费用可能无界。4. 实战应用场景与建模案例理解了算法我们来看看最大费用最大流能解决哪些有趣的问题。关键在于如何将“最大化某个正向指标”的需求建模成网络流中的“费用”。4.1 案例一最大利润运输问题问题描述你有若干个仓库源点和若干个市场汇点。每个仓库i有a_i单位的货物每个市场j有b_j单位的需求。从仓库i运输一单位货物到市场j会产生一个利润p_{ij}。你的目标是设计一个运输方案在满足所有市场需求或尽可能满足的前提下使得总利润最大。注意总运输量可能小于总供给或总需求目标是利润最大。建模方法超级源点与超级汇点建立一个超级源点S连接每个仓库i边的容量为仓库的供应量a_i费用为0。仓库到市场对于每个仓库i和市场j如果允许运输则建立一条边i - j容量为∞或一个足够大的数如min(a_i, b_j)费用为p_{ij}注意这是我们想要最大化的利润。市场到超级汇点连接每个市场j到超级汇点T边的容量为市场的需求量b_j费用为0。求解在这个网络上运行最大费用最大流。得到的最大流就是最优运输量最大费用就是最大总利润。变体与思考如果市场有最低需求限制怎么办这可以通过在“市场到汇点”的边上设置一个下限lower bound来处理或者拆点并用边容量来约束。4.2 案例二带权二分图的最大权匹配问题描述这是一个经典问题。有一个二分图左边是任务集合X右边是工人集合Y。将任务x_i分配给工人y_j会产生一个效益w_{ij}。每个任务最多分配给一个工人每个工人最多承担一个任务。目标是找到一个匹配使得被匹配的边数尽可能多最大匹配并且在所有最大匹配中总效益最大。建模方法超级源点与超级汇点建立超级源点S和超级汇点T。源点到任务S连接到每个任务节点x_i容量为1费用为0。任务到工人如果任务x_i可以分配给工人y_j则建立边x_i - y_j容量为1费用为w_{ij}效益。工人到汇点每个工人节点y_j连接到T容量为1费用为0。求解运行最大费用最大流。由于所有容量都是1得到的最大流值就是最大匹配数最大费用就是该匹配下的最大总效益。为什么是最大费用最大流因为我们需要先保证匹配数最大流量最大然后在这个前提下优化总效益费用最大。普通的匈牙利算法可以解决最大权匹配但最大费用最大流提供了一种不同的、易于扩展的思路例如处理任务和工人有多个容量时。4.3 案例三项目时间规划中的最大收益选择问题描述你有若干个项目每个项目i有一个开始时间s_i、结束时间e_i和完成后的收益v_i。你在同一时间只能进行一个项目。目标是选择一组在时间上不重叠的项目使得总收益最大。建模方法转化为最大费用最大流时间离散化将所有项目的开始和结束时间点排序得到一系列时间区间。构建链式网络创建一个时间链。设离散化后有t个时间点。创建节点T_1, T_2, ..., T_t。对于每个连续的时间段T_k - T_{k1}建立一条边容量为∞或你最多能并行进行的项目数这里是1费用为0。这条边代表“这段时间空闲”。项目作为边对于每个项目i找到其开始时间点对应的节点T_{s_i}和结束时间点对应的节点T_{e_i}。建立一条从T_{s_i}到T_{e_i}的边容量为1费用为v_i收益。这条边代表“进行这个项目消耗这段时间”。超级源点与超级汇点S连接到T_1容量为∞费用0。T_t连接到T容量为∞费用0。求解与解释在这个网络上跑最大费用最大流。由于“项目边”和“时间边”共享时间节点流量会从“时间边”被“挤”到“项目边”。因为每个项目边容量为1保证了每个项目最多被选一次。因为总流量要从S流到T它必须穿过整个时间链而选择项目边会获得正费用。算法会自动选择一组在时间上不冲突因为流守恒一个时间点流出的流量有限的项目使得总收益最大。最大流值就是所选项目覆盖的总时间或项目数量取决于建模细节最大费用就是总收益。这个建模非常巧妙它将时间资源抽象为网络中的容量将项目选择抽象为带有收益的边利用流的特性自动处理了冲突约束。5. 常见问题、调试技巧与优化建议即使有了模板在实际编码和调试中还是会遇到各种问题。下面分享一些我踩过的坑和总结的经验。5.1 为什么我的最大费用是负数/ 结果明显不对这是最常见的问题。可能的原因有费用累加错误确保你在累加费用时使用的是原始费用。在增广路径回溯时对于正向边累加flow * cost对于反向边累加flow * (-cost)。如果使用我模板中的公式flow * (dist[T] h[T] - h[S])要清楚dist[T]是重标定后的距离需要加上势能差才能得到原始费用和。最终记得对minCost取负得到maxCost。初始势能计算错误如果SPFA计算初始势能h时dist数组初始化为INF并且图中有些节点从S不可达那么这些节点的dist保持INF势能h就是INF。在后续Dijkstra中计算w cost h[u] - h[v]时如果h[u]或h[v]是INF会导致溢出或错误。建议将dist初始化为0。对于不可达节点SPFA后其dist可能仍为0如果所有边权非负或一个有限值这比INF安全得多。另一种做法是在Dijkstra中如果h[u]或h[v]为INF则跳过这条边因为这意味着该节点未参与初始势能计算理论上也不应在增广路径上。图构建错误这是最隐蔽的错误。仔细检查边的方向是否正确反向边的容量是否为0费用是否为正向边的相反数超级源点S和超级汇点T的设置是否正确是否所有需要流量的节点都正确连接了对于多源多汇问题是否正确地连接到了超级源汇存在正权环如果问题本身允许正权环即可以无限刷收益那么最大费用是无界的。你的算法可能陷入死循环或给出错误结果。在SPFA中加入负环检测如果检测到说明原问题无界。5.2 算法超时了怎么办对于大规模图节点数5000边数50000即使是Dijkstra优化版也可能压力很大。可以考虑以下优化使用更快的堆C中priority_queue默认是最大堆且比较慢。使用std::priority_queuepairll, int, vectorpairll, int, greater声明最小堆。对于极端情况可以考虑手写二叉堆或配对堆。势能算法的有效性确保使用了势能Dijkstra而不是纯SPFA。这是性能差距的关键。图的稀疏性使用链式前向星存图比vector邻接表在遍历时稍快。提前终止如果只需要最大费用而不需要严格的最大流比如在二分图最大权匹配中流量达到min(|X|, |Y|)即可可以在流量达到目标值时提前终止算法。容量缩放对于容量很大的情况可以考虑容量缩放Capacity Scaling技术每次只考虑容量大于某个阈值的边进行增广逐步降低阈值。这可以显著减少增广次数。问题特定优化很多问题有其特殊性质。例如在二分图最大权匹配中可以使用KM算法Kuhn-Munkres时间复杂度更低O(n^3)。5.3 如何处理负权边/正权环这是我们讨论的核心。总结一下目标为最大费用通常意味着原始边权为正收益我们将其取反得到负权。此时需要处理负权边。采用“SPFA初始化势能 Dijkstra增广”是标准做法。如果原始图中就存在负权边费用比如有些运输路径本身是赔钱的费用为负。那么即使我们求最小费用初始图也有负权边。此时同样需要先用SPFA计算初始势能或者全程使用SPFA。检测正权环负环在SPFA函数中记录每个节点的入队次数cnt[v]。如果cnt[v] n节点数则说明存在从源点可达的负环。在最大费用问题中这意味着存在正权环总费用可以无限增加问题可能无解或无界。5.4 一个实用的调试技巧当结果不对时不要急于看代码。先用手工构造一个非常小的样例比如3-4个节点2-3条边在纸上画出网络手动模拟算法过程计算势能、找增广路、更新流量和费用然后与程序输出对比。这是定位逻辑错误最有效的方法。另外在代码中关键步骤后添加打印输出比如每次增广后的流量、费用、势能数组h、距离数组dist等观察它们的变化是否符合预期。最大费用最大流是网络流中一个非常有力的工具它将“最大化收益”这一常见需求与强大的网络流算法结合了起来。理解其转化为最小费用流的本质掌握处理负权边的势能技巧再结合具体问题的巧妙建模你就能解决一大类看似复杂的优化问题。从“最小”到“最大”不仅仅是符号的改变更是思维角度的一次翻转。下次当你遇到需要最大化某个总和的问题时不妨想一想能不能把它画成一张图让流量带着“收益”流动起来