它們的差是不變的，

那么這個差分

約束系統中的所有不等式都不會被破壞。

差分約束系統的解法利用到了單源最短路徑問題中的三角形不等式。

即對于

任何一條邊

u?->?v

，都有：

d(v)

<=

d(u)

+

w(u,

v)

其中

d(u)

和

d(v)

是從源點分別到點

u

和點

v

的最短路徑的權值，

w(u,?v)

是邊

u?->?v

的權值。

顯然以上不等式就是

d(v)?-?d(u)?<=?w(u,?v)

。這個形式正好和差分約束

系統中的不等式形式相同。于是我們就可以把一個差分約束系統轉化成一張圖，

每個未知數

Xi

對應圖中的一個頂點

Vi

，把所有不等式都化成圖中的一條邊。對

于不等式

Xi?-?Xj?<=?c

，把它化成三角形不等式：

Xi?<=?Xj?+?c

，就可以化成

邊

Vj

->

Vi

，權值為

c

。最后，我們在這張圖上求一次單源最短路徑，這些三角

形不等式就會全部都滿足了，因為它是最短路徑問題的基本性質嘛。

話說回來，

所謂單源最短路徑，

當然要有一個源點，

然后再求這個源點到其

他所有點的最短路徑。

那么源點在哪呢？我們不妨自已造一個。

以上面的不等式

組為例，我們就再新加一個未知數

X0

。然后對原來的每個未知數都對

X0

隨便加

一個不等式

(這個不等式當然也要和其它不等式形式相同，

即兩個未知數的差小

總結

以上是生活随笔為你收集整理的约束rmq_差分约束的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。