8
20
2015
0

[心得]差分约束

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

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.

Category: 心得 | Tags: 图论 差分约束 | Read Count: 342

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com