图论笔记6：差分约束

1. 图论笔记——差分约束
1.1. 用途1.2. 问题转化1.3. 解决步骤1.4. 例题

1. 图论笔记6：差分约束
1.1. 用途
简单来说就是求一组不等式组的可行解： 例： x1 <= x2 + c1 x2 <= x3 + c2 x3 <= x1 + c3 … 差分约束可以求这样一组不等式可行解； 1.2. 问题转化 在最短路问题里，我们能发现，在更新dis数组时候我们会的到一个三角不等式 dis[v] <= dis[u] + w，那我们不妨把dis[v]看成x1，dis[u]看成x2，可以发现通过不断的更新最终dis[i]就会变成一个距离原点的最短距离，也就是原点到该最大值。为何是最大值？ 证明如下： 有不等式组如下： x1 <= x2 + c1 x2 <= x3 + c2 x3 <= x4 + c3 … xi-1 <= xi + ci 根据最短路的更新。 x1 <= xi + c

图论笔记6：差分约束最先出现在Python成神之路。