首页 > 代码库 > 差分约束系统

差分约束系统

唔,今天做题的时候发现了有这么一个概念。虽然不知道原理,但还是记录一下。

假设我们当前有四个等式:

 x1-x2<=k1;

 x2-x3<=k2;

 x1-x3<=k3;

 x3-x4<=k4;

然后求x1-x4的最大值,经过式子的变形,我们可以得到x1-x4<=k3+k4和x1-x4<=k1+k2+k4,由此可知x1-x4的最大值为min(k3+k4,k1+k2+k4)

则可以构建如下这幅图:

技术分享

很容易发现求x1-x4的最大值变成了求x4到x1的最短路。

如果求最大值,给出多组x-y>=k的式子,就连x到y的值为-k的路径,然后求x到y的最长路。即为答案。

如果题目中给出的是x-y<k要将式子变为x-y<=k-1

差分约束系统