C++怎么实现差分约束系统求解-C++-PHP中文网

差分约束系统本质是图的最短路径问题，通过构建有向边并引入超级源点运行bellman-ford或spfa判负环来求解可行解。

c++怎么实现差分约束系统求解

差分约束系统本质是图的最短路径问题

差分约束系统（如 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 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
}
</int>

SPFA 可提速但不改变逻辑，慎用 STL queue

SPFA 是 Bellman-Ford 的队列优化版本，平均更快，但最坏仍是 O(VE)。它不改变判负环逻辑：某个点入队次数 ≥ n+1（节点总数），就说明存在负环。注意 C++ 中不要用 std::queue 配合 count[] 数组简单判断——需严格统计「当前在队列中的节点被松弛的累计次数」，且入队前检查是否已达上限。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

用 vector<int> cnt(n + 1, 0)</int> 记录每个节点进队次数
每次从队列取出 u，对其邻边 u→v 松弛；若成功且 cnt[v] ，才将 <code>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 再算。