最靠谱方案是手写Dijkstra+势函数（Johnson重赋权）。因原始残量图含负权反向边，需用SPFA初始化势函数h[u]，再通过h[u]+=d[u]动态更新，确保每次Dijkstra在非负权图上正确求最短增广路。
最小费用最大流在C++里用什么库最靠谱
没有标准库实现，Boost.Graph 提供了 successive_shortest_path_nonnegative_weights，但接口绕、依赖重、编译慢；更常用的是手写 **SPFA + EK（Edmonds-Karp）** 或 **Dijkstra + 势函数（Johnson 重赋权）**。实际项目中，90% 的 C++ 工程师选择自己实现后者——因为可控、易调试、不引入外部依赖。
为什么不能直接用 Dijkstra 跑原始图求最短增广路
原始残量图中存在负权边（反向边费用为负），Dijkstra 会失效。必须先通过势函数 h[u] 对边权重赋值：w'(u→v) = w(u→v) + h[u] - h[v]，使其非负。这个 h 通常用第一次 SPFA 在初始残量图上求出的最短距离初始化，之后每次增广后用当前距离更新即可。
- 漏掉势函数更新 → 后续
Dijkstra算出错误路径，费用爆炸 - 初始化
h时没跑全图（比如只从源点出发但图不连通）→ 某些点h为无穷，重权后溢出或崩溃 - 反向边费用写成正数（应为
-cost）→ 费用累加方向反了，结果总为 0 或负得离谱
一个能过 OJ 的精简实现要点
以邻接表存图，每个边记录 to、cap、cost、rev（反向边下标）。注意：添加正向边时立刻添加反向边，且反向边 cap=0、cost=-cost。
- 用
priority_queue做堆，第一维是> d[u] + h[u]（即重权后距离），避免手写比较器出错 - 每次
Dijkstra后，对所有u执行h[u] += d[u]（前提是d[u]不是 INF），这是势函数递推的关键 - 增广时沿父指针回溯，流量取路径上最小残量，费用累加
flow * (原始边 cost)，别用重权后的值 - 开
long long存费用和距离，小数据用int容易在中间过程溢出
// 边结构示意（常见写法）
struct Edge {
int to, cap, cost, rev;
};
vector<vector>> graph;
</vector>
调试时最常卡住的三个地方
输出中间费用为负、最大流对但费用错、跑几轮就死循环——基本都是下面这三条之一没检查：
-
add_edge(u, v, cap, cost)调用两次：一次正向、一次反向，但反向边的rev指针没设对 → 流量更新时改错边 - 增广后没清空
prev_v[]和prev_e[]数组 → 下次Dijkstra误用旧父节点，路径拼错 - 判断是否还能增广时，只看
d[t] == INF，但没确保d[t]是重权后距离的最小值 → 实际还有路，却提前退出
势函数不是黑盒，它本质是把负权“摊”到节点上，让每条边看起来非负；一旦某个 h[u] 失准，整张图的重权就崩，后续所有 Dijkstra 都不可信。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
