差分约束算法
一.形式
由一组形如x_i−x_j≤c的不等式组成的系统，其中x_i,x_j,是变量，c是常量。
目标是：判断是否有一组 x 值同时满足所有约束；若有，求出一组可行解。
二.思路：转化成最短路问题
1.将x_i−x_j≤c转化成x_i≤c+x_j，添加一条j节点到i节点的权值为c的有向边。
2.添加一个超级源点s，使得s到每个节点都有一条权值为0的边，确保所有点可达。
3.执行最短路算法(spfa)
若存在负环，则无解，否则dis数组即为所求变量的一组合法解。
三.
1.若不等式符号为>=，只需对两边同时*1变形即可
2.这个算法的应用跟关键路径有很大关系(工程进度安排)
