城市速运公司「顺风快运」的调度员小周，摊开一张公路网：中央仓库 S 堆满包裹，要往终端门店 T 送货，中途可经中转站 A、B。每条路上都标着两行小字——一行是「最多同时过几辆货车」（容量），一行是「每辆货车收多少过路费」（费用）。老板下了死命令：门店要的货，能送多少就送多少（流量最大）；月底结算，过路费总账必须最低（费用最小）。既要满负荷，又要精打细算，这就是「最小费用最大流」问题。本文跟着小周一步步来：先学会把送货地图翻译成数学网络；再揭穿「每次都走最便宜的路」的贪心陷阱；认识地图上「越绕越赚钱」的返现怪圈（负圈）并清理它；最后请出 SPFA 和 Primal-Dual 两位「领航员」——一个负责在负费用地图上找路，一个负责把负数消灭、让 Dijkstra 极速上岗。故事讲完，你也就掌握了带费用约束的网络流系统求解方法。

岗位关联

学完本节，你就能独立建模「容量 + 费用」双约束的调度问题，并理解 SPFA 与 Primal-Dual 的工程取舍——这是物流调度、云带宽成本优化、编译器寄存器分配等场景通用的底层算法能力。

目录
  1. 可视化演示
  2. 费用网络建模：把送货地图变成数学账本
  3. 问题与最优性：什么才算「又满又省」
  4. 负圈检测处理：揪出地图上的「返现怪圈」
  5. SPFA 增广求路：队列式领航员
  6. 势函数重赋权：给城市挂上价格牌
  7. 原始对偶算法：修路与调价双管齐下
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

最小费用最大流在最大流基础上要求费用最小，常用SPFA或Primal-Dual算法求解。本文详解费用网络建模、... 切换模式查看不同维度。

本节配有交互动效（进入视口后自动加载，约 3KB）。

最小费用最大：核心原理 动态展示关键流程与数据流动 交互控件调节参数实时渲染 f(x) = transform(x) 核心概念的可视化呈现

费用网络建模：把送货地图变成数学账本

小周接到的第一项任务，是把公路网「翻译」成算法读得懂的账本。每个城市是一个节点，每条公路是一条有向边，边上钉着两个数字：容量（这条路最多能过几辆车）和单位费用（每过一辆车收多少过路费）。仓库 S 是源点，门店 T 是汇点，中间站 A、B 只是中转。小周在账本第一页写下：节点集合 V、边集合 E，以及每条边的容量表 c 和费用表 w。

这份「账本」在算法里叫费用网络。它和普通最大流网络唯一的区别，就是每条边多了一个「费用」维度。费用可以是每单位流量的运输成本、带宽单价、仓储租金……在 AI 与工程领域，凡是「有容量上限 + 有单位成本」的输送问题，都能套进这个框架。

形式化地，费用网络由 (V, E, c, w) 描述。流量 f(u,v) 表示边 (u,v) 上实际运输的单位数，它必须夹在 0 和容量 c(u,v) 之间；同时除源汇外，每个节点的「流入量 = 流出量」，这叫流量守恒。目标函数是所有边「单位费用 × 流量」的总和，我们希望它最小：

账本建好后，小周还会准备一张「实况地图」——残量网络。它记录每条路还剩多少空位（残量），并为每一个已占用的位置开一张「退款单」：反向边。反向边的容量就是已运输量，费用是原费用的相反数——意思是「如果反悔，可以退回这笔过路费」。有了退款单，车队就能在后续调度中悄悄改道，这正是最小费用最大流能跳出贪心陷阱的秘密武器。

min⁡∑(u,v)∈Ew(u,v) f(u,v)s.t.0≤f(u,v)≤c(u,v),∑u∈Vf(u,v)=∑u∈Vf(v,u)\displaystyle \min \sum_{(u,v)\in E} w(u,v)\, f(u,v) \quad \text{s.t.}\quad 0 \le f(u,v) \le c(u,v),\quad \sum_{u\in V} f(u,v) = \sum_{u\in V} f(v,u)
一句话：在每条路不超载、每个中转站不囤货的前提下，把总过路费压到最低。
  1. 目标函数（总费用）把每条边上的「单位费用 × 流量」全部加起来，得到全网络的总运输成本。
    ∑(u,v)∈Ew(u,v) f(u,v)\sum_{(u,v)\in E} w(u,v)\, f(u,v)
  2. 容量约束任意一条边上的流量不能是负数，也不能超过道路能承受的车流上限。
    0≤f(u,v)≤c(u,v)0 \le f(u,v) \le c(u,v)
  3. 流量守恒除源点 S 和汇点 T 外，每个中转站送进来的货必须和送出去的相等，不允许凭空多货或丢货。
    ∑u∈Vf(u,v)=∑u∈Vf(v,u)\sum_{u\in V} f(u,v) = \sum_{u\in V} f(v,u)

问题与最优性：什么才算「又满又省」

老板的指示有两层：第一层是「货要送够」（最大流），第二层是「钱要省够」（最小费用）。小周一开始的直觉是：每次都挑最便宜的路，把车队塞满开到黑。但他很快发现，有时候「最便宜的路先走到堵死」，反而把更便宜的后续组合给堵没了。光有直觉不够，需要一个能拍板的「最优性判据」。

在数学上，最小费用最大流分两个层次：先满足最大流（首要目标），再在所有最大流方案中挑费用最小的（次要目标）。算法正确性的核心，是一条漂亮的等价关系——最优性条件。

设当前流为 f，在残量网络 G_f 中，如果存在一个「总费用为负」的环（负费用圈），那么沿这个环把流量「绕一圈」，总流量不变，总费用却下降——说明当前 f 不是最优。反之，如果残量网络里找不到任何负圈，任何可行调整都无法再降低费用，当前流就是最小费用流。这就是消圈定理：

小周把这条定理贴在调度室里：每次调整完车队，用「扫圈」检查一遍地图，没有返现怪圈就收工，有就继续调。接下来他遇到的第一个麻烦，正是地图上真的冒出了返现怪圈——负圈。

当前流 f 是最小费用流  ⟺  Gf 中不存在负费用圈\displaystyle \text{当前流 } f \text{ 是最小费用流} \iff G_f \text{ 中不存在负费用圈}
直观理解：网络里只要还藏着「越绕越省钱」的循环，就说明还能降本；直到一个都找不到了，总账就再也压不下来。
  1. 当前流 f指现在已经安排在每条边上的运输方案，它必须满足容量约束和流量守恒。
    f:E→R≥0f: E \to \mathbb{R}_{\ge 0}
  2. 残量网络 G_f由「剩余正向容量 + 反向退款容量」拼成的新图，记录所有还能调整的空间。
    Gf=(V,Ef),Ef={(u,v)∣c(u,v)−f(u,v)>0}∪{(v,u)∣f(u,v)>0}G_f = (V, E_f), \quad E_f = \{(u,v) \mid c(u,v) - f(u,v) > 0\} \cup \{(v,u) \mid f(u,v) > 0\}
  3. 等价关系（iff）「没有负圈」和「费用最小」互为充要条件，可直接用来验证算法结果的对错。
    无负圈  ⟺  f 最优\text{无负圈} \iff f \text{ 最优}

负圈检测处理：揪出地图上的「返现怪圈」

有一天核算时，小周发现一条诡异环线：绕着走一圈，过路费加起来竟然是负数——不仅不交钱，还倒赚。现实中不可能有这种好事，但在残量网络里，「退款单」和「正向过路费」叠加，完全可能拼出一个总费用为负的环。这个环就叫负费用圈，简称负圈。

负圈的出现说明两件事：要么当前方案不是最优、还能继续省钱；要么输入数据本身有问题。无论哪种，都得先把它找出来。检测负圈最常用的工具就是 SPFA 或 Bellman-Ford：如果最短路算法执行了 |V| 轮之后仍然能松弛某条边，说明存在负圈——因为无负圈的图里，最短路最多经过 |V| - 1 条边。

找到负圈后要做「消圈」处理：沿圈找到能调整的最大量（瓶颈 δ），把圈上正向边的流量增加 δ、反向边的流量减少 δ。由于圈的「总费用」为负，每消一次圈，总费用就下降 δ 乘以圈的负费用：

小周把「查圈—消圈」做成例行公事，地图上再也没有返现怪圈。但每次用「扫全图」来找圈实在太慢。他灵机一动：与其事后消圈，不如一开始就保证每次增广都走在最便宜的路上——这就是连续最短路方法，而负责找路的，正是 SPFA 这位「队列式领航员」。

Δcost=δ×∑e∈Cw(e)<0\displaystyle \Delta \text{cost} = \delta \times \sum_{e \in C} w(e) < 0
意思是：绕着负圈每调整一轮，运费总账就「缩水」一圈，直到再也找不到负圈为止。
  1. 瓶颈 δ负圈上各条残量边的最小剩余容量，决定这一轮最多能「绕」多少流量。
    δ=min⁡e∈Cr(e)\delta = \min_{e \in C} r(e)
  2. 圈费用求和把环上所有边的单位费用加起来得到一个总费用；为负才是负圈。
    ∑e∈Cw(e)<0\sum_{e \in C} w(e) < 0
  3. 费用下降量消圈后总费用减少 δ × 圈费用的绝对值，这正是「返现」的金额，也就是降本的空间。
    Δcost=δ×∑e∈Cw(e)<0\Delta \text{cost} = \delta \times \sum_{e \in C} w(e) < 0

SPFA 增广求路：队列式领航员

每次派车队前，小周都要回答同一个问题：从仓库 S 到门店 T，眼下哪条路最便宜？难办的是，地图上有大量「退款单」（反向负费用边），普通导航 Dijkstra 一见到负数就罢工。小周改用 SPFA——一种用「待办队列」驱动的领航员：它不需要提前知道所有路的远近，谁的距离变了，就让谁重新进队检查一遍，像极了办公室里「谁手头数据更新了谁就举手汇报」的例会。

SPFA 是 Bellman-Ford 的队列优化版。Bellman-Ford 每一轮都把全部边扫一遍，太浪费；SPFA 观察到：只有「距离刚刚被更新」的节点，才可能让它的邻居继续变便宜，于是只把这些节点放进队列。平均复杂度接近 O(E)，最坏退化到 O(VE)，但工程上极快。

SPFA 维护距离数组 dist。初始化源点 dist[S]=0，其余为无穷大；节点 u 出队后，扫描它的每条出边 (u,v)，若 dist[u]+w(u,v) 比 dist[v] 更小，就更新 dist[v] 并把 v 入队（若 v 不在队中）。核心松弛式：

有了 SPFA，小周每一轮都能准确找到当前最便宜的送货路线，沿路把车队容量用到瓶颈，再更新残量网络和退款单，如此反复直到无路可走。这个过程就是「连续最短路增广」。但它有一个隐患：SPFA 虽然扛得住负权，遇上又长又绕的网络还是会被极端数据拖慢。小周下定决心：能不能把地图上的负数全部消灭，让 Dijkstra 这种「快导航」也能上岗？答案，就是给每个城市挂上一块「价格牌」。

dist[v]=min⁡{dist[v],  dist[u]+w(u,v)}\displaystyle \text{dist}[v] = \min\big\{\text{dist}[v],\; \text{dist}[u] + w(u,v)\big\}
一句话：如果「绕道 u 再走这条边」比 v 原来的距离更短，就更新 v 的距离，并安排 v 重新汇报。
  1. 距离数组 dist记录从源点 S 到每个城市当前已知的最少过路费。
    dist[S]=0,dist[v]=+∞  (v≠S)\text{dist}[S] = 0, \quad \text{dist}[v] = +\infty \; (v \ne S)
  2. 松弛操作比较「v 的原距离」和「u 的距离 + 边 (u,v) 的费用」，取更小的那个。
    dist[v]←min⁡(dist[v],dist[u]+w(u,v))\text{dist}[v] \leftarrow \min\big(\text{dist}[v], \text{dist}[u] + w(u,v)\big)
  3. 入队判定只有距离真的变小了的节点，才重新进入队列继续松弛它的邻居。
    v∉queue  ⇒  v 入队v \notin \text{queue} \;\Rightarrow\; v \text{ 入队}

势函数重赋权：给城市挂上价格牌

小周想出一个妙招：与其让领航员忍受负数，不如给每座城市挂一块「补贴价签」——势函数 h(v)。看路费时换算成「感知费用」：真实过路费 + 出发城价签 − 到达城价签。只要价签选得巧，所有感知费用都变成非负数。这样一来，地图上不再有「负数」，Dijkstra 这位快导航就能大显身手。

这套手法在算法界叫 Johnson 重赋权。它的数学魔力在于：对任意一条从 S 到 T 的路径，把所有边的「感知费用」加起来时，中间城市的价签恰好一加一减相互抵消，只剩下真实费用 + h(S) − h(T)，这是个与路径无关的常数。所以「感知费用」下的最短路，就是「真实费用」下的最短路——价格牌只改观感，不改事实。

定义重赋权后的费用（reduced cost）：

如果把 h(v) 取为「从参考源点到 v 的最短路长度」，那么由三角不等式 w(u,v) + h(u) ≥ h(v)，可推出所有边满足 w'(u,v) ≥ 0。这正是 Dijkstra 要求的非负边权条件。在连续增广过程中，我们每轮更新势函数，让残量网络（包括退款单）里的每条边都保持非负费用。

有了价格牌，领航员从「忍辱负重的 SPFA」升级为「轻装上阵的 Dijkstra」。小周把「调价签」和「派车队」拧成一股绳，交替进行——这正是 Primal-Dual 算法：一手抓原问题（车流），一手抓对偶问题（价签），双管齐下。

w′(u,v)=w(u,v)+h(u)−h(v)\displaystyle w'(u,v) = w(u,v) + h(u) - h(v)
核心结论：价格牌不改变任何一条路线的「真实总支出」，却把所有负的过路费都抹平了。
  1. 重赋权费用把真实费用加上出发城价签、减去到达城价签，得到「感知费用」。
    w′(u,v)=w(u,v)+h(u)−h(v)w'(u,v) = w(u,v) + h(u) - h(v)
  2. 路径不变性一路累加时中间价签全部抵消，S-T 路径总感知费用 = 真实费用 + h(S) − h(T)。
    ∑(u,v)∈Pw′(u,v)=∑(u,v)∈Pw(u,v)+h(S)−h(T)\sum_{(u,v)\in P} w'(u,v) = \sum_{(u,v)\in P} w(u,v) + h(S) - h(T)
  3. 非负条件h 取最短路距离时，由三角不等式保证所有 w' ≥ 0。
    h(v)≤h(u)+w(u,v)  ⟺  w′(u,v)≥0h(v) \le h(u) + w(u,v) \iff w'(u,v) \ge 0

原始对偶算法：修路与调价双管齐下

小周的调度室从此有了两条工作流：左手是「派车队」——在原网络里找最短路并增广流量；右手是「调价签」——每轮结束后更新各城市的补贴价签 h(v)。两条线交替运转：先派车，再调价，再派车……就像包工头一边修路一边调整补贴政策，让每一轮施工都走在当下最划算的路线上。这就是「原始对偶」的含义：原问题管车流，对偶问题管价格。

Primal-Dual 算法把势函数方法与连续最短路完美结合。它保证每一轮开始时，残量网络里所有边的 reduced cost 都 ≥ 0，于是可以直接用 Dijkstra 求最短路——比 SPFA 更快、更稳，且天然免除了负圈干扰。

算法框架如下：初始化 h(v)=0；每轮用 Dijkstra 在 reduced cost 下找 S→T 最短路；沿路增广瓶颈量 δ；然后更新势函数 h(v) ← h(v) + dist(v)，其中 dist(v) 是本轮 Dijkstra 算出的最短路距离；重复直到找不到路。更新势函数的妙处在于：本轮最短路树上的边 reduced cost 归零，而未松弛的边在新势下依然非负——不变量永远成立。

最终，小周的调度室形成了标准作业流程：SPFA 负责攻坚克难（处理负圈和初始带负费用的网络），Primal-Dual 负责日常高效运转（把负数消灭后用 Dijkstra 加速）。当增广到再也找不到 S→T 路径时，总流量达到最大；由于全程没有出现负圈，总费用也锁死在最小值。老板看着月底账单——流量拉满，成本最低，露出了满意的笑容。

h(v)←h(v)+dist(v),保证 w′(u,v)≥0 始终成立\displaystyle h(v) \leftarrow h(v) + \text{dist}(v), \qquad \text{保证 } w'(u,v) \ge 0 \text{ 始终成立}
每一轮「调价」都在为下一轮 Dijkstra 铺平道路，让地图永远保持「无负数」的友好状态。
  1. Dijkstra 增广在非负 reduced cost 下找最短路，取瓶颈流量增广，并更新残量网络。
    path=Dijkstraw′(S,T),δ=min⁡e∈pathr(e)\text{path} = \text{Dijkstra}_{w'}(S,T), \qquad \delta = \min_{e \in \text{path}} r(e)
  2. 势函数更新把每个城市的价格牌加上本轮它的最短路距离，使松弛过的边 reduced cost 归零。
    h(v)←h(v)+dist(v)h(v) \leftarrow h(v) + \text{dist}(v)
  3. 非负不变量更新后所有残量边的 reduced cost 仍 ≥ 0，下一轮 Dijkstra 可以无缝继续。
    w′(u,v)=w(u,v)+h(u)−h(v)≥0w'(u,v) = w(u,v) + h(u) - h(v) \ge 0

AI 应用场景

同城货运的智能调度

阶段：运筹优化 / 路径规划

解决的问题：传统人工调度凭经验排线，只能保证「车不空跑」，无法同时保证「货送最多、费用最低」。面对几十条线路的容量与单价组合，人工试错几乎不可能找到全局最优。用最小费用最大流建模后，系统能在秒级给出「各线路车次 + 货量」的全局最优方案。

具体案例：某同城货运平台把仓库设为源点、配送点设为汇点，每条道路标上「车辆容量上限」和「每趟单价」，用 SPFA/Primal-Dual 求解。上线后单车日均成本下降 18%，爆仓率下降 40%。

云计算数据中心的带宽成本优化

阶段：资源调度

解决的问题：虚拟机热迁移、大数据任务跨节点传输时，链路带宽有限且跨可用区流量要计费。既要最大化总吞吐量（最大流），又要最小化流量费用（最小费用）。MCMF 天然契合「带宽容量 + 单价」的建模方式。

具体案例：某云厂商在热迁移场景中用 MCMF 为每一批镜像传输规划路径，避开拥塞链路的同时把跨区流量费压到最低，迁移总耗时缩短 25%，网络账单下降 15%。

编译器后端的寄存器分配

阶段：编译优化

解决的问题：寄存器数量有限（容量），变量溢出到内存会有访存代价（费用）。编译器希望尽可能多的活跃变量留在寄存器中（最大流），同时 spill 的总代价最小（最小费用）。最小费用最大流把寄存器分配建模成一个带费用的网络流问题，供全局优化求解。

具体案例：LLVM 等编译器后端在寄存器合并（coalescing）与溢出位置选择中，使用最小费用流的变体建模求解，在保证正确性的前提下显著减少内存访问指令。

Python 演示

python80 行
from collections import deque  class MinCostMaxFlow:    def __init__(self, n):        self.n = n        self.g = [[] for _ in range(n)]     def add_edge(self, u, v, cap, cost):        # 正向边 [目标, 剩余容量, 单位费用, 反向边下标]        self.g[u].append([v, cap, cost, len(self.g[v])])        # 反向边=退款单: 容量0起步, 费用取负        self.g[v].append([u, 0, -cost, len(self.g[u]) - 1])     def spfa(self, s, t):        INF = float('inf')        dist = [INF] * self.n        inq = [False] * self.n        prev_v = [-1] * self.n        prev_e = [-1] * self.n        dist[s] = 0        q = deque([s])        inq[s] = True        while q:            u = q.popleft()            inq[u] = False            for i, e in enumerate(self.g[u]):                v, cap, cost, _ = e                if cap > 0 and dist[u] + cost < dist[v]:                    dist[v] = dist[u] + cost                    prev_v[v] = u                    prev_e[v] = i                    if not inq[v]:                        q.append(v)                        inq[v] = True        if dist[t] == INF:            return None        return dist, prev_v, prev_e     def solve(self, s, t):        flow = 0        cost = 0        while True:            res = self.spfa(s, t)            if res is None:                break            dist, prev_v, prev_e = res            d = float('inf')            v = t            while v != s:                u = prev_v[v]                d = min(d, self.g[u][prev_e[v]][1])                v = u            v = t            while v != s:                u = prev_v[v]                e = self.g[u][prev_e[v]]                e[1] -= d                self.g[v][e[3]][1] += d                v = u            flow += d            cost += d * dist[t]        return flow, cost  def main():    # 顺风快运网络: S=0, A=1, B=2, T=3    mcmf = MinCostMaxFlow(4)    mcmf.add_edge(0, 1, 3, 1)   # S -> A: 容量3, 单费1    mcmf.add_edge(0, 2, 2, 3)   # S -> B: 容量2, 单费3    mcmf.add_edge(1, 2, 2, 1)   # A -> B: 容量2, 单费1    mcmf.add_edge(1, 3, 3, 4)   # A -> T: 容量3, 单费4    mcmf.add_edge(2, 3, 4, 2)   # B -> T: 容量4, 单费2    flow, cost = mcmf.solve(0, 3)    print("max flow:", flow)    print("min cost:", cost)  if __name__ == "__main__":    main()
目的：用 SPFA 连续最短路增广实现最小费用最大流，求解「顺风快运」网络的 5 单位最大流，并输出最小总费用 23。
  1. self.g[v].append([u, 0, -cost, len(self.g[u]) - 1])建反向边就是开「退款单」：容量从 0 起步，费用取负，留给未来的反悔操作。
  2. if cap > 0 and dist[u] + cost < dist[v]:松弛的核心条件：「这条路还能走」且「绕道更便宜」才更新距离。
  3. if not inq[v]: q.append(v)SPFA 的队列优化：只把「身价变了」的节点重新请回队列，避免全量扫描。
  4. d = min(d, self.g[u][prev_e[v]][1])沿前驱链回退，找出整条路的最小剩余容量，即瓶颈 δ。
  5. e[1] -= d; self.g[v][e[3]][1] += d一减一加完成增广：正向扣容量，反向补「退款额度」。
  6. cost += d * dist[t]瓶颈量 × 本路最小费用，滚入总账。

常见误区

误区每次都找当前最便宜的路，把这条路能送的量一次送满，一直送到不能再送，最后总费用肯定最低。

正解不对。把「最便宜的路」一次塞满，可能把更优组合需要的容量挤占掉。正确做法是每轮只增广「瓶颈量」，并通过反向边（退款单）允许后续改道。以文中网络为例：若先把 S→A→T 送满 3 单位，总费用是 25；而先走 S→A→B→T 送 2 单位，再补 S→A→T 1 单位、S→B→T 2 单位，总费用只要 23。贪心「送满」与「最优」的差距，恰恰在于是否允许反悔重路由。

为何常见：「便宜的路先抢到手」符合日常直觉，容易让人忽略网络流中边与边互相挤占容量的耦合关系。

误区残量网络里出现费用为负的边，肯定是建模或程序出 bug 了。

正解恰恰相反，负费用反向边是算法的核心机制。它代表「撤销之前流量并退回过路费」，费用为负是数学上的必然——退款当然是「负数」。「负权」在这里不是异常，而是反悔能力。SPFA 和 Bellman-Ford 正因为支持负权边才被选作残量网络的最短路引擎；Dijkstra 必须先经势函数重赋权把边权变非负才能上岗。

为何常见：初学者先学 Dijkstra 时被告知「不能处理负权」，于是把「负权」直接等同于「非法输入」，没意识到那是算法的边界而不是世界的边界。

误区给每条边加上 h(u) - h(v) 这种调整项，算出来的总费用肯定不对了。

正解不会。重赋权只是换了一副眼镜看路费：对任意一条 S-T 路径，中间节点的价签一加一减全部抵消，总「感知费用」= 真实费用 + h(S) - h(T)，这是一个与路径无关的常数。所有路径同时平移同一个常数，谁最省钱的排序完全不变，所以最短路和最小费用都不变。h 只是计算工具，从不进入最终账单。

为何常见：容易把数学技巧当成真实成本，没有理解「整体平移不改变大小关系」这一层。

误区消圈法和连续最短路增广法是两种完全无关的算法，只能分开背。

正解它们本质是同一个最优性判据（残量网络无负圈）的两副面孔。消圈法：随便给一个可行流，反复找负圈并消掉，直到没有负圈；连续最短路法：每轮沿最短路增广，配合势函数保证 reduced cost 非负，从源头上不制造负圈。两条路殊途同归，最终都收敛到无负圈状态，即最小费用最大流。

为何常见：教材通常分两章、按「题型」讲授，学生容易停留在记忆层面，没抓住背后统一的判据与对偶关系。

面试题

Q1. 最小费用最大流的优化目标，正确的表述是？

单选题 · easy

  • A.在保证流量最大的前提下，使总费用最小← 正确答案
  • B.在保证总费用最小的前提下，使流量最大
  • C.使每条边的平均单位费用最低
  • D.使源点到汇点的路径最短

答案：A。最小费用最大流是「两步走」：先保证从源到汇的总流量达到最大（首要目标），再在所有最大流方案中挑总费用最小的。B 把主次颠倒，费用降下来了流量却没拉满；C 是「平均费用」低，与总账无关；D 是单源最短路问题，根本不需要考虑容量。就像顺风快运：先保证门店的货一定送够，再比哪种调度方案最省钱。

Q2. 残量网络中反向边的费用为什么通常为负？

单选题 · easy

  • A.纯粹的数学推导必然结果，没有物理含义
  • B.为了让 SPFA 算法运行得更快
  • C.表示「退款」：撤销之前的流量，可以收回这部分过路费← 正确答案
  • D.为了处理容量为 0 的边

答案：C。反向边对应「撤销之前已运输的流量并退回过路费」，费用取原费用的相反数，所以为负。它让算法具备「反悔改道」能力——后续增广可以通过反向边悄悄修正之前不够优的安排。A 把数学形式当成了无意义符号；B、D 张冠李戴。类比：退款单上写着 -5 元，不是系统出错，而是告诉你退掉这一单能省回 5 元。

Q3. 判断一个可行流是否为最小费用流的最优性条件是？

单选题 · mid

  • A.所有边上的流量都达到容量上限
  • B.残量网络中不存在负费用圈← 正确答案
  • C.每条增广路径的单位费用相同
  • D.源点的所有出边都满流

答案：B。消圈定理说：残量网络无负费用圈 ⇔ 当前流是最小费用流。A 只要求「压满」但不管费用；C、D 与最优性没有直接关系。就像小周的调度室：只要地图上还藏着「越绕越省钱」的返现怪圈，总账就还能降；彻底找不到负圈，才是真正的底线价。

Q4. 下列哪个算法组合最适合用来「检测负圈」？

单选题 · mid

  • A.Dijkstra + 优先队列
  • B.SPFA 或 Bellman-Ford← 正确答案
  • C.并查集 + 最小生成树
  • D.快速排序 + 二分查找

答案：B。负圈检测依赖「最短路还能被持续松弛」这一特征：如果算法执行 |V| 轮后仍有边能松弛，说明存在负圈。SPFA/Bellman-Ford 都支持负权边，天然适配；Dijkstra 遇负权直接失效，A 不可行；C、D 是无关的数据结构或排序工具，与这件事毫无关系。

Q5. 势函数重赋权（Johnson 技巧）保证的核心性质是？

单选题 · mid

  • A.所有原边的费用都归零
  • B.所有 S-T 路径的长度变得相等
  • C.流量守恒方程自动成立
  • D.调整后所有边的 reduced cost 非负← 正确答案

答案：D。Johnson 重赋权的核心是把势函数 h 取作最短路距离，由三角不等式可推出所有 reduced cost ≥ 0，这正是 Dijkstra 的启动条件。A 是误解（费用不会归零）；B 是另一个错误想象；C 是流量守恒，与重赋权无关。类比：价格牌选得巧，地图上所有「负数过路费」都被抹平，导航仪才能放心跑 Dijkstra。

Q6. 关于 SPFA 的优化，下列说法正确的有？

多选题 · mid

  • A.只有距离被更新的节点，才重新入队继续松弛← 正确答案
  • B.用队列替代 Bellman-Ford 每轮全量扫描← 正确答案
  • C.能够处理带负权边的残量网络← 正确答案
  • D.时间复杂度一定优于 O(VE)

答案：ABC。SPFA 是 Bellman-Ford 的队列版：只有距离被更新的节点（「身价变了」的城市）才重新入队，避免全量扫描；它天然支持负权边，适合残量网络。D 错在把「平均很快」夸大成「一定更快」，最坏情况下 SPFA 仍是 O(VE)。

Q7. 为什么 Johnson 重赋权 w'(u,v)=w(u,v)+h(u)-h(v) 不会改变 S-T 最短路？

单选题 · hard

  • A.任意 S-T 路径的总调整量恒为 h(S)-h(T)，与路径无关← 正确答案
  • B.每条边的费用都被变成了相同的常数
  • C.势函数 h 是随机生成的，统计上不影响结果
  • D.只有正权边被修改，负权边保持不变

答案：A。沿任意 S-T 路径把 reduced cost 累加，中间城市的 h(u) 与 -h(v) 恰好一加一减全部抵消，只剩真实费用 + h(S) - h(T)，这是个常数。常数平移不改变路径之间的相对大小，所以最短路不变。B、C、D 都没有抓住「级数相消」这个关键。就像所有商品统一加 10 元服务费，谁贵谁便宜的顺序不会变。

Q8. 一次增广中算出的瓶颈容量 δ 的含义是？

单选题 · mid

  • A.这条增广路恰好必须运送 δ 单位
  • B.这条增广路最多能运送 δ 单位，通常就增广 δ 单位← 正确答案
  • C.整个网络总共还能运送 δ 单位
  • D.每条边的费用都变为原来的 δ 倍

答案：B。瓶颈 δ 是增广路上所有残量边的最小剩余容量，表示这条路「一次最多能塞多少货」。连续最短路算法每轮就按 δ 增广，然后更新残量网络与反向边。A 误把「上限」当「必须值」；C 混淆了「一条路的瓶颈」和「全网剩余」；D 张冠李戴。

Q9. 关于「消圈法」与「连续最短路增广法」，正确的说法有？

多选题 · hard

  • A.消圈法：先有可行流，再反复消除负圈直到无圈← 正确答案
  • B.增广法：每轮走最短路并增广，配合势函数保证不产生负圈← 正确答案
  • C.两种方法都建立在「无负圈即最优」的判据上← 正确答案
  • D.两种方法得到的最大流量值不同

答案：ABC。两个算法家族共享同一判据「无负圈即最优」。消圈法是「先给可行流，再消负圈」；连续最短路法是「每轮走最短路，配合势函数让 reduced cost 非负，从源头不制造负圈」。两者殊途同归，最大流量值当然相同，D 错。

Q10. 在最小费用最大流中，「费用 w(u,v)」的单位含义是？

单选题 · easy

  • A.从源点到这条边起点的路径总长度
  • B.网络中节点数量的多少
  • C.算法的迭代轮数
  • D.单位流量通过该边的代价← 正确答案

答案：D。w(u,v) 表示「单位流量通过边 (u,v) 的代价」，总费用 = Σ（流量 × 单位费用）。A 混淆了最短路里的「距离累加」；B 是节点数；C 是算法开销，都不是目标函数里的费用。就像每辆货车的过路费按「车次」收，不按「城市数」收。