差分约束系统本质是图的最短路径问题，通过构建有向边并引入超级源点运行Bellman-Ford或SPFA判负环来求解可行解。
差分约束系统本质是图的最短路径问题
差分约束系统（如 x_j - x_i ≤ c）能直接转成有向边 i → j，权值为 c 的图；求一组可行解，等价于在该图上跑单源最短路。只要图中没有负环，就存在解；否则无解。注意：不能假设所有变量都 ≥ 0 或有默认初值——必须引入超级源点 s，连边 s → i 权值为 0（即 x_i - x_s ≤ 0），再以 s 为起点跑 Bellman-Ford 或 SPFA。
用 Bellman-Ford 判负环并求解（C++ 实现要点）
Bellman-Ford 是标准解法，因差分约束图边数通常不多、但可能含负权，且需检测负环。关键不是“求最短距离”，而是用松弛操作探测是否还能更新——若第 n 轮（n 为变量总数）仍可松弛，说明存在负环，无解。
- 把每个变量编号为
0到n-1，超级源点设为n - 建边时，约束
x_u - x_v ≤ w→ 加边v → u（注意方向！因为x_u ≤ x_v + w对应dist[u] ≤ dist[v] + w） -
dist数组初始化为一个大数（如INT_MAX/2），但dist[super] = 0 - 做
n+1轮松弛：前n轮正常更新，第n+1轮若仍有更新，即存在负环
vector<int> dist(n + 1, INT_MAX / 2);
dist[n] = 0; // super source
for (int i = 0; i <= n; i++) { // n+1 rounds
bool updated = false;
for (auto& [u, v, w] : edges) { // u->v with weight w
if (dist[u] != INT_MAX / 2 && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
updated = true;
}
}
if (i == n && updated) return false; // negative cycle
}
SPFA 可提速但不改变逻辑，慎用 STL queue
SPFA 是 Bellman-Ford 的队列优化版本，平均更快，但最坏仍是 O(VE)。它不改变判负环逻辑：某个点入队次数 ≥ n+1（节点总数），就说明存在负环。注意 C++ 中不要用 std::queue 配合 count[] 数组简单判断——需严格统计「当前在队列中的节点被松弛的累计次数」，且入队前检查是否已达上限。
- 用
vector<int> cnt(n + 1, 0)记录每个节点进队次数 - 每次从队列取出
u，对其邻边u→v松弛；若成功且cnt[v] < n + 1，才将v入队并cnt[v]++ - 一旦
cnt[v] == n + 1，立刻返回无解 - 避免用
std::queue存重复节点却不控频次——这会导致误判或死循环
常见错误：不等式方向搞反、漏建超级源点、忽略溢出
最容易错的是约束转边方向：x_a - x_b ≤ c 必须写成 b → a 权 c，而不是 a → b。漏掉超级源点会导致部分变量不可达，dist 保持极大值，后续判断失效。另外，dist 初始化用 INT_MAX 直接加权会溢出，必须用 INT_MAX / 2 或 1e9 等安全值；SPFA 中也要防止 dist[u] + w 溢出，建议先判 dist[u] != INF 再算。
立即学习“C++免费学习笔记（深入）”；
负环存在性比具体解更重要——很多题目只问“是否有解”，此时只需跑完 Bellman-Ford 第 n+1 轮看是否还能松即可，不必保留最终 dist 值。变量实际取值就是 dist[i]（相对于 x_s = 0），但要注意这组解只是其中一种可行解，不是唯一解。
