Different Constraints - 差分约束
问题
差分约束是这样一类线性约束：
上面的不等式可以转化为线性不等式：
进一步抽象为：
矩阵有行列，每一行有且仅有一个和一个，其余所有值都是。未解数矩阵有行列，依次为。常熟矩阵有行列，依次为。
第行不等式满足：
其中，等于或，且。
这样的线性不等式组称为差分约束。
对于上面的差分约束，存在一组解：
对于任意常数，都有解：
即该差分约束的通解。
给定矩阵以及行数列数，求差分约束的解。
解法
差分约束是最短路径在线性规划上的典型应用之一。将差分约束转化为有向图。
将所有不等式转化为有向图的边，权值为，共条边个顶点。再额外增加顶点，且顶点到其他个顶点都存在边，权值为，共条边。最终有向图有个顶点条边。
通过Bellman Ford算法求出到其他所有顶点的最短路径。若其中存在某个顶点的最短路径，则说明该图不存在最短路径，对应的差分约束也不存在解；否则即为差分约束的解。即差分约束的解为：
该算法的时间复杂度与Bellman Ford算法相同，也是。