差分约束中，x_i - x_j ≤ c 转化为图的边核心是改写为 x_i ≤ x_j + c，对应从 j 到 i、权值为 c 的有向边；方向与权值错误会导致解不满足原不等式。
差分约束不等式怎么转成图的边
核心是把每个 x_i - x_j ≤ c 形式的约束，改写为 x_i ≤ x_j + c，再对应一条从节点 j 指向节点 i、权值为 c 的有向边。
常见错误是方向搞反：写成 i → j 或权值用 -c，结果跑出来 dist 值完全不满足原始不等式。记住口诀：“≤ 右边变量是起点，左边变量是终点”。
遇到其他形式要先标准化：
-
x_i - x_j ≥ c→ 转成x_j ≤ x_i - c→ 边i → j，权-c -
x_i = x_j + c→ 拆成两个：x_i ≤ x_j + c和x_j ≤ x_i - c→ 两条边，权分别为c和-c -
x_i ≤ c（常数约束）→ 引入虚拟源点0，加边0 → i，权c
为什么必须加超级源点
不加的话，图可能不连通，某些变量之间没路径，Bellman-Ford 或 SPFA 就没法松弛到所有边，导致部分约束被忽略——不是“无解”，而是“漏判”。
超级源点 0 需满足：从它出发能到达图中每一条边（不要求到达每个点）。最稳妥做法是，对每个变量节点 i（1~n），都加一条 0 → i 边，权值通常设为 0（若已有常数上界，可设为对应上界值）。
注意：设权为 0 时，最终解 dist[i] 必然 ≤ 0；若想让解更“自然”（比如允许正数），可在建图后统一平移，但负环判断不受影响。
用 Bellman-Ford 还是 SPFA 判负环
两者都能用，但行为差异明显：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
Bellman-Ford：固定松弛n轮（n为节点总数），第n轮还能更新 → 存在负环 → 无解 -
SPFA：用队列优化，但需额外记录每个节点入队次数；若某节点入队 ≥n次 → 存在负环
关键陷阱：SPFA 的 cnt[v] >= n 判断必须放在更新 dist[v] 之后、入队之前；否则可能漏判。另外，初始化 dist[0] = 0，其余为 INF（如 0x3f3f3f3f），不能全设为 0。
性能上，SPFA 平均快，但最坏仍是 O(n×m)；若图稀疏且负环概率低，优先用 SPFA；若追求稳定性和易调试，用 Bellman-Ford 更直接。
跑完最短路后，dist[i] 是什么
dist[i] 就是一组可行解：代入原不等式组，全部成立。
但要注意两点：
- 它不是唯一解——所有
dist[i] + k（k 为任意实数）仍是解；差分约束系统一旦有解，必有无穷多解 - 它给出的是“最大可能值”：因为
dist[i]是从源点出发、满足所有 ≤ 约束的最小上界，所以这组解让每个x_i尽可能大（在约束下）
如果题目要求的是某个差值（如 x_n - x_1）的最大值，那直接输出 dist[n] - dist[1] 即可——这正是最短路路径长度的物理意义。
真正容易被忽略的，是“超级源点连边权值”的选择：它不只影响解的偏移量，还隐式设定了所有变量的公共上界基准；若权值设得过大（比如全设 1e9），可能掩盖真实负环；过小（比如全设 -1e9），又可能导致溢出或误判。稳妥做法是按实际约束设，没有显式上界时才统一用 0。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
