夜深人静写算法（4）：差分约束

文章预览

（点击 上方公众号 ，可快速关注） 来源： 英雄哪里出来  cppblog.com/menjitianya/archive/2015/11/19/212292.html 如有好文章投稿，请点击 → 这里了解详情 目录 一、引例 1、一类不等式组的解 二、最短路 1、Dijkstra 2、图的存储 3、链式前向星 4、Dijkstra + 优先队列 5、Bellman-Ford 6、SPFA 7、Floyd-Warshall 三、差分约束 1、数形结合 2、三角不等式 3、解的存在性 4、最大值 => 最小值 5、不等式标准化 四、差分约束的经典应用 1、线性约束 2、区间约束 3、未知条件约束 五、差分约束题集整理 一、引例 1、一类不等式组的解 给定n个变量和m个不等式，每个不等式形如 x[i] – x[j] < = a[k] (0 < = i, j < n, 0 < = k < m， a[k]已知)，求 x[n-1] – x[0] 的最大值。例如当n = 4，m = 5，不等式组如图一- ………………………………