SPFA能直接处理负权费用因专为含负权边的单源最短路设计，MCMF残量图中反向边天然带负费用，且无负环时可正确求出最小费用增广路。
SPFA为什么能直接处理负权费用
因为费用流中的“费用”本质上是图上边的权重，而SPFA本就是为含负权边的单源最短路设计的。只要残量网络里没有负环（MCMF建模下初始图无负环，且每次增广后仍保持无负环），SPFA就能正确算出从源点到汇点的最小费用增广路。
关键点在于：MCMF中每条反向边的费用是原边费用的相反数（-cost），所以残量图天然可能出现负权边——这正是SPFA的适用场景。
- 不用预处理、不用势函数，初始化距离数组后直接跑
SPFA即可 - 需额外记录前驱节点（
pre[]）和流入边（pre_edge[]）用于后续增广 - 每次成功找到增广路后，要沿路径更新正向边剩余容量，并给反向边加容量，同时累加总费用
- 注意判断是否可达：若
dist[t]仍为无穷大，说明已无增广路，算法终止
Dijkstra必须用势函数（Johnson）才能用
原始Dijkstra不能处理负权边，但MCMF残量图中反向边必然带负费用，所以必须先“平移”所有边权使其非负，且不改变最短路的相对顺序。这就是势函数（h[]）的作用。
势函数h[v]通常取为上一轮SPFA（或首次用SPFA）求出的源点到各点的最短距离。之后每条边(u→v)的新权值定义为：cost[u][v] + h[u] - h[v]。这个变换保证新权≥0，且任意路径的权值变化量只依赖端点，不影响最短路选择。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 第一次必须用
SPFA初始化h[]（因为初始图可能含负权边） - 后续每次调用
Dijkstra前，都要用上一轮的dist[]更新h[]：即h[v] += dist[v]（累加形式，等价于维护当前势） -
Dijkstra中松弛条件要还原：比较的是dist[u] + cost[u][v] + h[u] - h[v]，但实际代码里常把势差合并进边权预计算 - 用
priority_queue时注意：C++默认大根堆，需用greater<pair>></pair>或取负；距离值建议用long long防溢出
SPFA vs Dijkstra：什么时候选哪个
不是“哪个更快”，而是“哪个更稳”。稠密图、小数据、存在较多负权边时，SPFA写起来简单、不易错；而稀疏图、大数据（如顶点数≤1e4，边数≤5e4）、需要稳定复杂度时，带势函数的Dijkstra更可靠——SPFA最坏O(VE)可能被卡成超时。
- ACM/ICPC比赛中，若没明确卡SPFA，优先写
SPFA版MCMF，调试成本低 - 工业级代码或在线判题平台（如LOJ、Codeforces Gym）中出现最坏数据，
Dijkstra + 势函数是唯一选择 - 注意：势函数版本中，
h[]不能初始化为0！否则Dijkstra会因负权边失效；必须由首次SPFA提供初值 - 反向边费用始终是
-original_cost，与势无关；势只用于重赋权，不改变实际费用累加逻辑
常见错误：势函数更新错位或忘记重赋权
最典型的两个坑：一是把h[]当成固定值，多次Dijkstra后不再更新；二是Dijkstra内部用了新权值松弛，但增广时却用原始cost算费用，导致总费用错误。
- 每次
Dijkstra返回后，必须执行：for (int i = 1; i - 增广路径上的费用累加，永远使用原始边的
cost字段（不是重赋权后的值） - 建图时务必确保：正向边
cost为题目给定值，反向边cost为-cost，且两者cap初始分别为c和0 - 如果用邻接表存边，推荐把
cost作为边结构体成员，避免和重赋权混淆；重赋权值仅用于Dijkstra内部比较，不覆盖原值
实际写的时候，负权不是用来“消除”的，是靠算法适配或数学变换让它变得可解。势函数那几行代码看着绕，但漏掉任何一处，结果就全错——尤其是h的迭代更新，最容易在多组数据或多次调用时被忽略。
