关于差分约束

灌水区

ningago @ 2022-04-07 15:47:24

众所周知，差分约束抽象出的最短路模型没用规定的源点，使用加了一个超级源点：

    for(int i = 1;i <= n;i++)
        add(S,i,0);

这个式子相当于dis_i - dis_S \leq 0 的限制，由于 dis_S = 0，所以有了 dis_i \leq 0

那么对于有 dis_S \geq 0 限制的题目该如何改进使得最短路模型仍然有用

by Dr_Gilbert @ 2022-04-07 15:58:12

@ningago
类似这道题 CF67A
可以仍然这样去做，最后输出 dis_S 的相反数

by ningago @ 2022-04-07 15:59:34

@Dr_Gilbert

这样推不等式的过程需要修改吗qwq

by Dr_Gilbert @ 2022-04-07 16:14:16

@ningago 注意推不等式时，推的变量实际上是距离的相反数。
例如 CF67A，以 a_i<a_{i+1} 为例，推的是 -dis_{i+1}-(-dis_i)\le-1 即 dis_i\le dis_{i-1}-1。

by ningago @ 2022-04-07 16:14:49

@Dr_Gilbert %%%%%

|