逻辑理解:
把xi<=xj+c 看成j−>i花费wc 的边(边的定义)
那么此时在满足所有限制的情况下求最短路就能满足此性质。
(满足所有限制就是从超级原点出发 遍历所有边)
求一遍最短路。
如何判断无解呢? 有负环就等价于无解。
有负环就无解。无解一定是xi<=xj+c(c<0)的情况,这也对应无解。故等价。
于是就可以找出一组解。
求最小值最长路。最大值最短路。
求最大值:
一定是xi<=xj+c形式。最大值等价于枚举i的所有链式关系上界取最小值。(对xi的限制就这么多)
而根据上述公式,每一个不等式链等价于一条1~i路径。(根据边的定义,不等式链就是1~i的路径。1~i的路径也可以根据边的定义就是不等式链,且一一对应(不对应就与边的定义矛盾了))
那么 求最大值就等价于所有路径的最小值。即最短路。
求最小值:
一定是xi>=xj+c形式。最小值等价于枚举i的所有链式关系下界取最大值。
同样链式关系对应一条1~i路径。
也就是求所有路径的最大值。即最长路。