TsReaper's Blog

之前学习差分约束的时候有两个问题一直没有弄明白：不等式是怎么转换为图的？以及到底要算最长路还是最短路呢？这篇心得就来解决这两个问题。并介绍常见的用于构造不等式的限定关系。

1、不等式是怎么转换为图的？

先来考虑这个不等式：a-b ≤ c。

我们知道，对于最短路，有这样的不等式：dis(u) ≤ dis(v) + len(v,u) （v,u是由一条长度为len(v,u)的有向边连接的两个点，dis(v)与dis(u)表示起点到达v或u的最短路）。

变形得：dis(u) - dis(v) ≤ len(v,u)，与a-b ≤ c是不是非常相似？

所以，对于形如a-b ≤ c的不等式，我们可以从点b向点a连接一条长度为c的边。这样，我们就可以把不等式转换为图。

2、构造出图之后，到底是算最短路还是最长路呢？

由于a-b ≤ c转化为图利用了最短路不等式，所以如果不等式组都是形如a-b ≤ c的不等式，就算最短路。相似地，a-b ≥ c可以由最长路不等式转换为图，那么算的就是最长路。

3、如果不等式组里的不等式并不全是≤号怎么办呢？

只要移项就可以了！比如a-b ≥ c，移项后就变成b-a ≤ -c~

4、有哪些限定关系可以构造不等式呢？

a比b至多多c：a-b ≤ c；

a比b至少多c：a-b≥c；

a与b相等：a-b ≤ 0 且 a-b ≥ 0；

a比b恰好多c：a-b ≤ c 且 a-b ≥ c.