國家集訓(xùn)隊2006集

1、v 在面對多種多樣的問題時，我們經(jīng)常會碰到這樣的情況：往往我們能夠根據(jù)題目題面意思來建立一些簡單的模型，但卻面對這些模型無從下手。這時我們應(yīng)該意識到，也許能夠?qū)⑦@種模型與其他的模型之間搭起一座橋梁，使我們能夠用更簡單直接的方式解決它。這里我們介紹一種方法，它很好地將某些特殊的不等式組與圖相聯(lián)結(jié)，讓復(fù)雜的問題簡單化，將難處理的問題用我們所熟知的方法去解決，它便是差分約束系統(tǒng)差分約束系統(tǒng)。這里我們著重介紹差分約束系統(tǒng)差分約束系統(tǒng)的原理和其需要掌握的bellman-ford算法。然后通過zju1508和zju1420兩道題目解析差分約束系統(tǒng)在信息學(xué)題目中的應(yīng)用，并逐漸歸納解決這類問題的思考方向。 v

2、算法簡單介紹算法簡單介紹 這個算法能在更一般的情況下解決最短路的問題。 一般在： 1.該算法下邊的權(quán)值可以為負(fù) 2.可以運(yùn)用該算法求有向圖的單元最長路徑或者最短路徑 . 3. v松弛技術(shù)松弛技術(shù)： 對每一個結(jié)點v，逐步減小從起點s到終點v最短路的估計量distv直到其達(dá)到真正的最短路徑值mindistv。 以單元最短路徑為例這個操作就是保證 distvdistu+wu,v then distv=distu+wu,v 如果是最長路徑則是保證distv=distu+wu,v v偽代碼如下偽代碼如下：For i=1 to |V|G|-1 Do for 每條邊(u，v) Do 更新操作（u，v，w（u

3、，v）For 每條邊（u，v） Do if 仍然有可更新內(nèi)容 then return FalseReturn TrueMAXMAXMAXMAX06785-2-4-3792ST6MAX7MAX06785-2-4-3792ST647206785-2-4-3792ST247206785-2-4-3792ST圖例中，S為源節(jié)點，粗線段覆蓋的邊表示最近一次執(zhí)行更新操作的邊。算法執(zhí)行|V|-1次操作，每次操作都對所有可以進(jìn)行松弛操作的邊進(jìn)行擴(kuò)展。v最終狀態(tài)如下圖。247-206785-2-4-3792STv證明算法的正確性證明算法的正確性 1設(shè)G=（V，E）為有向加權(quán)圖，源節(jié)點為S，加權(quán)函數(shù)為w：E-R。

4、如果有負(fù)權(quán)回路則Bellman-ford算法一定會返回布爾值false,否則返回TRUE。 2設(shè)G=（V，E）為有向加權(quán)圖，源節(jié)點為S加權(quán)函數(shù)為w：E-R，并且G不含從s可達(dá)的負(fù)權(quán)回路，則算法Bellman-ford終止時，對所有從s可達(dá)的結(jié)點v有dv=mindist（s，v）。v對于解決差分約束系統(tǒng)問題的操作過程和使用原理，我們通過下面一道簡單的題目進(jìn)行了解。v引例：Zju1508 Interval 題目大意：有一個序列，題目用n個整數(shù)組合 ai，bi，ci來描述它，ai，bi，ci表示在該序列中處于ai，bi這個區(qū)間的整數(shù)至少有ci個。如果存在這樣的序列，請求出滿足題目要求的最短的序列長度

5、是多少。如果不存在則輸出 -1。v輸入：第一行包括一個整數(shù)n，表示區(qū)間個數(shù)，以下n行每行描述這些區(qū)間，第i+1行三個整數(shù)ai，bi，ci，由空格隔開，其中0=ai=bi=50000 而且 1=ci=C的形式，我們從A向B連一條有向邊，權(quán)值為 -C。 1)Sbi-Sai-1=Ci 2)Si-Si-1=0 3)Si-1-Si=-1 這樣圖就能完整地描述本題了！用Bellman-ford求解！201345611111000000-1-3-2例1S4-S0=2S6-S2=3S3-S1=1v這樣如果我們從V0出發(fā)，求出結(jié)點V0到Vn的最短路徑，則Sn-S0為滿足要求情況下的最小值。相反如果我們發(fā)現(xiàn)在Be

6、llman-ford算法執(zhí)行的過程中存在有負(fù)權(quán)回路，則說明不存在滿足要求的式子。v于是通過合理的建立數(shù)學(xué)模型，將不等式圖形化，用Bellmanford作為武器，最終此題得到了圓滿的解決！v線性程序設(shè)計線性程序設(shè)計： 我們?yōu)榫€性程序設(shè)計問題制定一個嚴(yán)格的數(shù)學(xué)描述： 給定一個m*n矩陣A，維向量b和維向量c，我們希望找出由n個元素組成的向量x，在由Ax=b所給出的m個約束條件下，使目標(biāo)函數(shù) 達(dá)到最大值。n1iiixcv其實很多問題都可以通過這樣一個線性程序設(shè)計框架來進(jìn)行描述。在實際的問題中，也經(jīng)常要對其進(jìn)行分析和解決。上述例題使我們對這一類線性程序設(shè)計問題提供了一個多項式時間的算法。它將一類特殊的

7、線性不等式與圖論緊密聯(lián)系在了一起。這類特殊的線性不等式，我們稱它為差分約差分約束系統(tǒng)束系統(tǒng)，它是可以用單元最短路徑來求解的。v差分約束系統(tǒng)差分約束系統(tǒng)： 差分約束系統(tǒng)是一個線性程序設(shè)計中特殊的一種，線性程序設(shè)計中矩陣A的每一行包含一個1和一個-1，A的所有其他元素均為0。由Ax=b給出的約束條件形成m個差分約束的集合，其中包含n個未知單元。每個約束條件均可夠成簡單的不等式如下：xj-xi=bk（1=i,j=n,1=k=m）v簡單舉例：3-3-1-4511-0 xxxxx 110001010001100010010010110010100010001154321v找出未知量 x1,x2,x3,x

8、4,x5,并且滿足以下差分約束條件： x1-x5=-1 x2-x5=1 x3-x1=5 x4-x1=-1 x4-x3=-1 x5-x3=-3 x5-x4=-3需要注意的是，用Bellmanford求出的具體答案只是眾多答案中的一種，答案并不唯一，但答案之間卻也有著聯(lián)系。這里我們并不對其進(jìn)行專門的探討。v例題三 zju1420 Cashier Employment 出納員問題vTehran的一家每天24小時營業(yè)的超市，需要一批出納員來滿足它的需要。超市經(jīng)理雇傭你來幫他解決他的問題超市在每天的不同時段需要不同數(shù)目的出納員（例如：午夜時只需一小批，而下午則需要很多）來為顧客提供優(yōu)質(zhì)服務(wù)。他希望雇傭最

9、少數(shù)目的出納員。 經(jīng)理已經(jīng)提供你一天的每一小時需要出納員的最少數(shù)量R(0), R(1), ., R(23)。R（0）表示從午夜到上午1：00需要出納員的最少數(shù)目，R（1）表示上午1：00到2：00之間需要的，等等。每一天，這些數(shù)據(jù)都是相同的。有N人申請這項工作，每個申請者I在沒24小時中，從一個特定的時刻開始連續(xù)工作恰好8小時，定義tI （0 = tI = 23）為上面提到的開始時刻。也就是說，如果第I個申請者被錄取，他（她）將從tI 時刻開始連續(xù)工作8小時。 你將編寫一個程序，輸入R（I）（I = 0.23）和tI （I = 1.N），它們都是非負(fù)整數(shù)，計算為滿足上述限制需要雇傭的最少出納員

10、數(shù)目。在每一時刻可以有比對應(yīng)的R（I）更多的出納員在工作。 v輸入 輸入文件的第一行為測試點個數(shù)（= 20）。每組測試數(shù)據(jù)的第一行為24個整數(shù)表示R（0），R（1），.， R（23）（R（I）= 1000）。接下來一行是N，表示申請者數(shù)目（0 = N = 1000），接下來每行包含一個整數(shù)tI （0 = tI = 23）。兩組測試數(shù)據(jù)之間沒有空行。 輸出 對于每個測試點，輸出只有一行，包含一個整數(shù)，表示需要出納員的最少數(shù)目。如果無解，你應(yīng)當(dāng)輸出“No Solution”。 v我們按剛才所講到的方法對此題進(jìn)行處理。這題很容易想到如下的不等式模型： 設(shè)num i 為i時刻能夠開始工作的人數(shù)，x i

11、 為實際雇傭的人數(shù)，那么x I =r I 設(shè)s I =x 1 +x 2 +x I ， 得到 0=s I -s I-1 =num I ， 0=I=r I ， 8=I=r I ， 0=I=連接的式子 vs I -s I-1 =0 (0=I=-num I (0=I=r I (8=I=r I -s 23 (0=I=C 的式子 我們從節(jié)點B 引出一條有向邊指向 A 邊的權(quán)值為C （這里注意由于左右確定，式子又是統(tǒng)一的=的不等式，所以A和B是相對確定的，邊是一定是指向A的） ，圖就建成了 。 最后枚舉所有s 23 的可能值，對于每一個s23，我們都進(jìn)行一次常規(guī)差分約束系統(tǒng)問題的求解，判斷這種情況是否可行，如果可行求出需要的最優(yōu)值，記錄到An