---恢復內容開始---

轉自：http://www.cnblogs.com/void/archive/2011/08/26/2153928.html

?

差分約束系統(tǒng)中：

?

如果求未知數(shù)的最大值，那么按小于等于建圖后求最短路即可。（因為求最短路是由無窮向下約束而得到的，所以得到的一定是最大值）。

?

如果求未知數(shù)的最小值，那么按小于等于建圖后求最長路即可。

?

注意所有數(shù)據(jù)的關系，不能漏掉關系，還有與附加源點的關系。

?

如果是按大于等于建圖：

?

求最大值，建圖后求最長路；

?

求最小值，建圖后求最短路。

?

因為大于等于建圖后，相當于未知數(shù)都 * -1了，所以求出結果后需要 * -1。

①：對于差分不等式，a - b <= c ，建一條 b 到 a 的權值為 c 的邊，求的是最短路，得到的是最大值?
②：對于不等式 a - b >= c ，建一條 b 到 a 的權值為 c 的邊，求的是最長路，得到的是最小值?
③：存在負環(huán)的話是無解?
④：求不出最短路（dist[ ]沒有得到更新）的話是任意解?

一直不知道差分約束是什么類型題目，最近在寫最短路問題就順帶看了下，原來就是給出一些形如x-y<=b不等式的約束，問你是否滿足有解的問題

好神奇的是這類問題竟然可以轉換成圖論里的最短路徑問題，下面開始詳細介紹下

比如給出三個不等式,b-a<=k1,c-b<=k2,c-a<=k3,求出c-a的最大值,我們可以把a,b,c轉換成三個點，k1，k2，k3是邊上的權，如圖

由題我們可以得知，這個有向圖中，由題b-a<=k1,c-b<=k2,得出c-a<=k1+k2,因此比較k1+k2和k3的大小，求出最小的就是c-a的最大值了

根據(jù)以上的解法，我們可能會猜到求解過程實際就是求從a到c的最短路徑，沒錯的....簡單的說就是從a到c沿著某條路徑后把所有權值和k求出就是c -a<=k的一個

推廣的不等式約束，既然這樣，滿足題目的肯定是最小的k，也就是從a到c最短距離...

理解了這里之后，想做題還是比較有困難的，因為題目需要變形一下，不能單純的算..

首先以poj3159為例,這個比較簡單，就是給出兩個點的最大差，然后讓你求1到n的最大差，直接建圖后用bellman或者spfa就可以過了

稍微難點的就是poj1364，因為他給出的不等式不是x-y<=k形式，有時候是大于號，這樣需要我們去變形一下，并且給出的還是>,<沒有等于，都要變形

再有就是poj1201，他要求出的是最長距離，那就要把形式變換成x-y>=k的標準形式

注意點:

1. 如果要求最大值想辦法把每個不等式變?yōu)闃藴蕏-y<=k的形式,然后建立一條從y到x權值為k的邊,變得時候注意x-y<k =>x-y<=k-1

?? 如果要求最小值的話,變?yōu)閤-y>=k的標準形式，然后建立一條從y到x的k邊，求出最長路徑即可

2.如果權值為正，用dj，spfa，bellman都可以，如果為負不能用dj，并且需要判斷是否有負環(huán)，有的話就不存在

?

?

?

轉自：http://www.cnblogs.com/pony1993/archive/2012/09/01/2666996.html

---恢復內容結束---

在一個差分約束系統(tǒng)(system of difference constraints)中，線性規(guī)劃矩陣A的每一行包含一個1和一個-1，A的其他所有元素都為0。因此，由Ax≤b給出的約束條件是m個差分約束集合，其中包含n個未知量，對應的線性規(guī)劃矩陣A為m行n列。每個約束條件為如下形式的簡單線性不等式：xj-xi≤bk。其中1≤i,j≤n，1≤k≤m。

例如，考慮這樣一個問題，尋找一個5維向量x=(xi)以滿足：

?

?

這一問題等價于找出未知量xi，i=1,2,…,5，滿足下列8個差分約束條件：

x1-x2≤0

x1-x5≤-1

x2-x5≤1

x3-x1≤5

x4-x1≤4

x4-x3≤-1

x5-x3≤-3

x5-x4≤-3

????該問題的一個解為x=(-5,-3,0,-1,-4)，另一個解y=(0,2,5,4,1)，這2個解是有聯(lián)系的：y中的每個元素比x中相應的元素大5。

?
引理：設x=(x1,x2,…,xn)是差分約束系統(tǒng)Ax≤b的一個解，d為任意常數(shù)。則x+d=(x1+d,x2+d,…,xn+d)也是該系統(tǒng)Ax≤b的一個解。

?

約束圖

???在一個差分約束系統(tǒng)Ax≤b中，m X n的線性規(guī)劃矩陣A可被看做是n頂點，m條邊的圖的關聯(lián)矩陣。對于i=1,2,…,n，圖中的每一個頂點vi對應著n個未知量的一個xi。圖中的每個有向邊對應著關于兩個未知量的m個不等式中的一個。

???給定一個差分約束系統(tǒng)Ax≤b，相應的約束圖是一個帶權有向圖G=(V,E)，其中V={v0,v1,…,vn}，而且E={ (vi,vj) : xj-xi≤bk是一個約束}∪{ (v0,v1) , (v0,v2) , … , (v0,vn) }。引入附加頂點v0是為了保證其他每個頂點均從v0可達。因此，頂點集合V由對應于每個未知量xi的頂點vi和附加的頂點v0組成。邊的集合E由對應于每個差分約束條件的邊與對應于每個未知量xi的邊(v0,vi)構成。如果xj-xi≤bk是一個差分約束，則邊(vi,vj)的權w(vi,vj)=bk（注意i和j不能顛倒），從v0出發(fā)的每條邊的權值均為0。

??
定理：給定一差分約束系統(tǒng)Ax≤b，設G=(V,E)為其相應的約束圖。如果G不包含負權回路，那么x=( d(v0,v1) , d(v0,v2) , … , d(v0,vn) )是此系統(tǒng)的一可行解，其中d(v0,vi)是約束圖中v0到vi的最短路徑(i=1,2,…,n)。如果G包含負權回路，那么此系統(tǒng)不存在可行解。

?

差分約束問題的求解

???由上述定理可知，可以采用Bellman-Ford算法對差分約束問題求解。因為在約束圖中，從源點v0到其他所有頂點間均存在邊，因此約束圖中任何負權回路均從v0可達。如果Bellman-Ford算法返回TRUE，則最短路徑權給出了此系統(tǒng)的一個可行解；如果返回FALSE，則差分約束系統(tǒng)無可行解。

???關于n個未知量m個約束條件的一個差分約束系統(tǒng)產生出一個具有n+1個頂點和n+m條邊的約束圖。因此采用Bellman-Ford算法，可以再O((n+1)(n+m))=O(n^2+nm)時間內將系統(tǒng)解決。此外，可以用SPFA算法進行優(yōu)化，復雜度為O(km)，其中k?為常數(shù)。

轉載于:https://www.cnblogs.com/xuyanqd/p/8762762.html

總結

以上是生活随笔為你收集整理的【转】 差分约束系统详解（转化为最短路） （概念）的全部內容，希望文章能夠幫你解決所遇到的問題。

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