首页 > 其他 > 详细

差分约束系统

时间:2017-06-20 10:40:00      阅读:283      评论:0      收藏:0      [点我收藏+]

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

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

 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

差分约束系统

原文:http://www.cnblogs.com/2014nhc/p/7052890.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!