顺便问一句，为什么差分约束中求最大解是跑最短路，求最小解是跑最长路？
by mot1ve @ 2021-03-04 15:22:20
用 -x2 带入 x2 就可以用了
by wheneveright @ 2021-03-04 15:37:13
@[wqy_03](/user/250699)
个人认为差分约束可以将所有的不等号方向相同
之后看题目要求跑最短、长路
by legendgod @ 2021-03-04 16:28:36
@[wqy_03](/user/250699) 时隔1h我都不知道我该不该回了
就是差分约束求最小解是 $a_i+c\leq a_j$ ，则 $i$ 向 $j$ 连长度为 $c$ 的边，那么 $s$ 到 $j$ 的一个路径相当于对 $a_j$ 的一个约束，最长路相当于对 $a_j$ 下界最紧的一个界，也就相当于是一堆类似 $a_j\geq p_k$ 的约束，求解得求 $p_i$ 最大的那个，所以得跑最长路
然后求最大解因为建边方向反了，类似的分析一下就好了
by w23c3c3 @ 2021-03-04 16:32:03
@[wheneveright](/user/189351) 这里变量不是要作为图中的点吗，怎么能成负的啊
by mot1ve @ 2021-03-04 16:37:31
@[w23c3c3](/user/109942) 感谢回复
by mot1ve @ 2021-03-04 16:42:46