icontofig | 发布于 2019-08-18 19:27:53 | 阅读量 241 | 差分约束系统
发布于 2019-08-18 19:27:53 | 差分约束系统
CCPC 2017-2018 Finals HDU 6252 Subway Chasing 差分约束系统
题目大意两个人从家里出发,Panda比Sheep晚走x分钟,在地铁上两人保持m次通信,每次通信Panda在a和b之间,Sheep在c和d之间。到终点后,求问每两站之间所需要的时间是多少,如果无法计算输出IMPOSSIBLE 题解我们可以在草稿纸上画画图,把两人的位置之间连线,标记上表示这一段的时间为x。 然后我们可以看到两者区间两端点的关系,进行分类讨论: 如果a = b: 1.c = d 那么就是c - a = x,也就是c - a <= x, c - a >= x,也即 c - a  <= x,a - c <= -x; 2.c ≠ d 则c - a <
继续阅读
icontofig | 发布于 2019-02-13 09:33:40 | 阅读量 305 | 最短路 差分约束系统
发布于 2019-02-13 09:33:40 | 最短路 差分约束系统
[转载]差分约束系统详细讲解
差分约束系统 一、何为差分约束系统:差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。比如: 二、差分约束系统的求解:差分约
继续阅读