算法合集之淺析差分約束系統(tǒng)

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

2、系統(tǒng)在信息學(xué)題目中的應(yīng)用，并逐漸歸納解決這類問題的思考方向。目錄關(guān)鍵字【2】Bellman-ford 算法【2】算法簡(jiǎn)單介紹【2】算法具體流程【2】例題一 ZJU2008 【4】差分約束系統(tǒng)【5】例題二ZJU1508 【5】線性程序設(shè)計(jì)【7】差分約束系統(tǒng)【7】 例題三 ZJU1420 【8】結(jié)語【9】附錄【9】關(guān)鍵字 差分約束系統(tǒng)、不等式、單元最短路徑、轉(zhuǎn)化正文在分析差分約束系統(tǒng)之前，我們首先介紹一個(gè)解決單元最短路徑問題的Bellman Ford算法，它的應(yīng)用十分廣泛，在差分約束系統(tǒng)中更充當(dāng)著重要的角色。Bellman-ford 算法算法簡(jiǎn)單介紹這個(gè)算法能在更一般的情況下解決最短路的問題。何謂

3、一般，一般在該算法下邊的權(quán)值 可以為負(fù)，可以運(yùn)用該算法求有向圖的單元最長(zhǎng)路徑或者最短路徑。我們這里僅以最短路徑為例。Bellman ford類似于Dijkstra算法，對(duì)每一個(gè)節(jié)點(diǎn) vW V，逐步減小從起點(diǎn) s到終點(diǎn)v最 短路的估計(jì)量distv直到其達(dá)到真正的最短路徑值mindistv。Bellman-ford算法同時(shí)返回一個(gè)布爾值，如果不存在從源結(jié)點(diǎn)可達(dá)的負(fù)權(quán)回路，算法返回布爾值 TRUE，反之返回FALSE。算法具體流程1. 枚舉每條邊(u,v) E (G)。2. 對(duì)枚舉到的邊進(jìn)行一次 更新操作。3. 回到步驟1,此過程重復(fù)n-1次，以確定沒有更可以優(yōu)化的情況。4. 枚舉每條邊(u, v)

4、若仍然存在可以 更新的邊，貝U說明有向圖中出現(xiàn)了負(fù)權(quán)回路， 于是返回布爾值 FALSE。5. 返回布爾值TRUE。注：這里的更新操作是一種松弛技術(shù)，以單元最短路徑為例這個(gè)操作就是保證 distv<=distu+wu,v,即 if distv>distu+wu,v then distv=distu+wu,v ,如果是最長(zhǎng)路徑則是保證 distv>=distu+wu,v。定義一個(gè)有向圖 G= (V , E), w (u, v)表示由結(jié)點(diǎn)u到v的邊的權(quán)值。偽代碼如下：For i=1 to |V|G|-1Do for 每條邊(u , v)亡 E|G|Do 更新操作(u , v, w

5、( u , v)For 每條邊(u , v) £ E|G|Do if 仍然有可更新內(nèi)容then return FalseReturn True卜圖描述了該算法的操作過程，粗線條代表已更新線段52.設(shè)G= (V , E)為有向加權(quán)圖,圖例中，S為源節(jié)點(diǎn)，粗線斷覆蓋的邊表 示最近一次執(zhí)行更新操作的邊。算法執(zhí)行|V|-1 次操作，每次操作都對(duì)所有可以進(jìn)行松弛操作 的邊進(jìn)行擴(kuò)展。證明一下Bellman-Ford算法的正確性。1.設(shè)G= (V, E)為有向加權(quán)圖，源節(jié) 點(diǎn)為S,加權(quán)函數(shù)為 w: E-> R。如果有負(fù)權(quán) 回路則Bellman_ford算法一定會(huì)返回布爾值 false，否則返

6、回TRUE。SS5MAXMAX664-3687027027MAXMAX7729-3-4Bellman_fordw: E-> R,并且G不含從s可達(dá)的負(fù)權(quán)回路，則算法證明略。源節(jié)點(diǎn)為S加權(quán)函數(shù)為終止時(shí)，對(duì)所有從s可達(dá)的結(jié)點(diǎn)v有dv=mindist (s, v)。證明：設(shè)v為從s可達(dá)的節(jié)點(diǎn)，且p=<v0,v1,.,vk>為從s到v的一條最短路徑，其中v0=s, vk=v。因?yàn)槁窂絧是簡(jiǎn)單路徑，所以 k<=|V|-1。我們希望通過歸納證明對(duì)i=0,1,k,在對(duì)G的邊進(jìn)行完第i趟操作后有dvi=mindist(s,vi),且該等式此后一直保持成立，因?yàn)榭偣灿?|V|-1次操作，

7、所以上述結(jié)論證明命題成立。我們發(fā)現(xiàn)與Dijkstra不同，Bellman ford更多的是對(duì)邊進(jìn)行操作，在稀疏圖，即點(diǎn)多邊 少的圖中，用Bellman Ford更能高效的解決單元最短路徑問題。下面一道例題來進(jìn)一步熟悉Bellman Ford并與Dijkstra作一下簡(jiǎn)單的時(shí)間上的比較。例題一：ZJU2008 Invitation Cards題目大意在有向加權(quán)圖中 G (V , E),郵局要從起點(diǎn) S向其他n個(gè)節(jié)點(diǎn)發(fā)送郵件，于 是派出n個(gè)郵遞員，分別到達(dá)其他 n個(gè)地點(diǎn)發(fā)送，然后回到起點(diǎn) S,求出所有郵遞員所經(jīng)過 的總路程的最小值。數(shù)據(jù)范圍1 <= P,Q <= 1000000。P表示

8、節(jié)點(diǎn)數(shù)目，Q表示邊的個(gè)數(shù)。題目分析這道題算法很簡(jiǎn)單， 即求出從s到任意點(diǎn)的最短路徑， 求其和ANS1 ,再將所 有有向邊反向(這個(gè)過程將求從另外 n個(gè)結(jié)點(diǎn)到s的最短路徑轉(zhuǎn)化為從 s到其他n個(gè)點(diǎn)的最 短路徑)，再求一次s到任意點(diǎn)的最短路徑，求其和 ANS2 , Ans=Ans1+Ans2即為所求。2但是，此題難在數(shù)據(jù)重上，無論是Dijkstra的O(V )的算法，還是Bellmanford的O(VE)的算法都無法在數(shù)據(jù)規(guī)模最大的情況下在5s的時(shí)間內(nèi)得出結(jié)果，于是需要做出一點(diǎn)優(yōu)化。關(guān)于Dijkstra的優(yōu)化：用堆維護(hù)使尋找需要擴(kuò)展的點(diǎn)的過程復(fù)雜度降低為1。復(fù)雜度大幅降低。關(guān)于Bellman for

9、d的優(yōu)化：可以將 Bellman ford需要擴(kuò)展的點(diǎn)放進(jìn)隊(duì)列中，擴(kuò)展順序有了新的變化。用一個(gè)隊(duì)列queue表示需要更新的點(diǎn)，每次取隊(duì)列頭指針fp所指的點(diǎn)u,搜索所有的邊(u,v)屬于E,如果distu+wu,v比distv更優(yōu)則更新distv,尾指針rp后挪一位， 將v點(diǎn)加入隊(duì)列 queue。這樣的優(yōu)化避免了很多重復(fù)的操作，事實(shí)證明它的效率僅次于 Dijkstra+heap的效率。下面用3種不同的方法來解這道題目，看看結(jié)果如何。我們用以下三種方法求最短路徑：1. Dijkstra2. Bellman Ford3. Dijkstra&Heap在ZJU Online Judge中進(jìn)行評(píng)測(cè)

10、結(jié)果如下：算法運(yùn)行所有數(shù)據(jù)所用時(shí)間Dijkstra> 5s (TLE)Bellman Ford1.46sDijkstra&Heap1.24s差分約束系統(tǒng)對(duì)于解決差分約束系統(tǒng)問題的操作過程和使用原理，我們通過下面一道簡(jiǎn)單的題目進(jìn) 行了解。引例：例題二Zju1508 Interval題目大意：有一個(gè)序列，題目用 n個(gè)整數(shù)組合ai,bi,ci來描述它，ai, bi, ci表示在該序列中處于ai, bi這個(gè)區(qū)間的整數(shù)至少有ci個(gè)。如果存在這樣的序列，請(qǐng)求出滿足題目要求的最短的序列長(zhǎng)度是多少。如果不存在則輸出-1。輸入：第一行包括一個(gè)整數(shù)n,表示區(qū)間個(gè)數(shù)，以下 n行每行描述這些區(qū)間，第 i

11、+1行三個(gè)整數(shù) ai, bi, ci,由空格隔開，其中 0<=ai<=bi<=50000 而且 1<=ci<=bi-ai+1 。輸出：一行，輸出滿足要求的序列的長(zhǎng)度的最小值。淺析初看此題感覺無從下手，我們將范圍和個(gè)數(shù)進(jìn)行量化，讓問題看起來更加簡(jiǎn)單些。將問題數(shù)字化：1如果i存在于序列之中右記,t i = 0如果i不存在于序列中b i那么本題約束條件即為 ' t j _ c i (i = 1,2,., n) j -a i建立不等式模型：i這樣的描述使一個(gè)約束條件所牽涉的變量太多，不妨設(shè)Si =乏tj (i=1,2,n)j約束條件即可用以下不等式表示：Sbi -

12、 Sai_1 - ci(i = 1,2,., n)值得注意的是，這樣定義的S若僅僅滿足約束條件的要求是不能完整體現(xiàn)它的意義的，S中的各個(gè)組成之間并不是相對(duì)獨(dú)立的，他們存在著聯(lián)系。i由于Si =£ tj ,且t要么為1,要么為0,則Si 一定比Si-1大，且至多大1。于是有： j=1Si - Si - 0(i = 1,2,., n)Si-1 一Si - - 1(i = 1,2,., n)那么如何找到滿足要求的這樣一組S,且使其個(gè)數(shù)最少呢？這里我們看到最少就會(huì)聯(lián)想到貪心，確實(shí)這道題目用貪心可行，且不失為一種很好的做法，但在這里我們不作多的介紹。我們將針對(duì)這個(gè)不等式組進(jìn)行聯(lián)想，遷移。注意到

13、不等式中只涉及到了 2個(gè)未知數(shù)，用減號(hào)相連接。這樣的式子是否與過去曾經(jīng)學(xué)過的Bellmanford中的松弛操作所達(dá)到的效果相類似呢？聯(lián)想：我們需要尋找一個(gè)滿足以下要求的S數(shù)組S bi - Saj _1- Ci (Ii = 1 ,2,.,n )S i - S i _1 一 0 (i =1,2,.,n )Si-1 - Si _ - 1(i =1,2 ,.,n )而 Bellman-Ford每次的更新操作為Ifdu wu, v - dv thendv du wu, v即在經(jīng)過若干次更新操作將要保證dv<=du+wu,v這里我們也有一個(gè)已知量 -邊的權(quán)值，即 wu,v,于是整理一下得du-dv&

14、gt;=wu,v經(jīng)過這樣的變形，不難看出，兩個(gè)式子有著極為驚人的相似！于是做出如下的轉(zhuǎn)化：1. 我們將 S°,Si,.,Sn ,看作 n+1 個(gè)點(diǎn) V°,Vi,.,Vn。2. 若Si和Sj之間有著約束關(guān)系，例如Si-1-Si>= -1,那么我們從結(jié)點(diǎn) V向結(jié)點(diǎn)V連上一條有向邊，邊的權(quán)值為 -1。這樣如果我們從 V。出發(fā)，求出結(jié)點(diǎn)V。到Vn的最短路徑，貝U Sn為滿足要求情況下的最小值。相反如果我們發(fā)現(xiàn)在Bellmanford算法執(zhí)行的過程中存在有負(fù)權(quán)回路，則說明不存在滿足要求的式子。于是通過合理地建立數(shù)學(xué)模型，將不等式圖形化，用 Bellmanford作為武器，最終此

15、題 得到了圓滿的解決！思考：本題只要求輸出最少的個(gè)數(shù)，那么能否通過上述方法構(gòu)造出相應(yīng)的數(shù)列呢？答案是肯 定的。其實(shí)在 Bellmanford的過程中，我們已經(jīng)得到了所有結(jié)點(diǎn)上S的值，那么由=Si-S-求出所有T,當(dāng)Ti為1則輸出i,即可輸出滿足題目要求的序列?？偨Y(jié)：對(duì)于ZJU1508的問題，最終可以化為一類線性不等式定義的線性函數(shù)。而這類問題其 實(shí)是可以轉(zhuǎn)化為單元最短路徑問題，從而用剛才所準(zhǔn)備到的Bellman Ford算法來解決它。線性程序設(shè)計(jì)：我們?yōu)榫€性程序設(shè)計(jì)問題制定一個(gè)嚴(yán)格的數(shù)學(xué)描述：給定一個(gè)m*n矩陣A ,維向量b和維向量c,我們希望找出由 n個(gè)元素組成的向量 x,在由Ax<=

16、b所給出的m個(gè)約束條件下，使目標(biāo)函數(shù)Z。烏乂達(dá)到最大值。其實(shí)很多問題都可以通過這樣一個(gè)線性程序設(shè)計(jì)框架來進(jìn)行描述。在實(shí)際的問題中， 也經(jīng)常要對(duì)其進(jìn)行分析和解決。上述例題使我們對(duì)這一類線性程序設(shè)計(jì)問題提供了一個(gè)多項(xiàng) 式時(shí)間的算法。它將一類特殊的線性不等式與圖論緊密聯(lián)系在了一起。這類特殊的線性不等式，我們稱它為差分約束系統(tǒng)，它是可以用單元最短路徑來求解的。差分約束系統(tǒng)：差分約束系統(tǒng)是一個(gè)線性程序設(shè)計(jì)中特殊的一種，線性程序設(shè)計(jì)中矩陣A的每一行包含一個(gè)1和一個(gè)-1, A的所有其他元素均為 0。由Ax<=b給出的約束條件形成 m個(gè)差分約 束的集合，其中包含n個(gè)未知單元。每個(gè)約束條件均可夠成簡(jiǎn)單的不

17、等式如下：Xj -Xjbk(1<=I,j<=n,1<=k<=m )簡(jiǎn)單舉例:一11I 0-1-1| 00.0-101000000000001001-11-100-10-1-100011一0父X2X3X4夕-1154-1-3找出未知量X1,X2,X3,X4 , X5 ,并且滿足以下差分約束條件:X1X2： =0X 1 - X 5= -1X2-X5：=1X3-X1： =5X4-X1：=4X4-X3：=-1X5-X3:：=-3X5一X4'：=-3需要注意的是，用Bellmanford求出的具體答案只是眾多答案中的一種，答案并不唯一,但答案之間卻也有著聯(lián)系。這里我們并不

18、對(duì)其進(jìn)行專門的探討。了解了差分約束系統(tǒng)的整個(gè)過程，下面再看另外一道題目，讓我們對(duì)差分約束系統(tǒng)的 應(yīng)用能夠有更加深刻的認(rèn)識(shí)。例題三zju1420 Cashier Employment 出納員問題題目中文翻譯：Tehran的一家每天24小時(shí)營(yíng)業(yè)的超市，需要一批出納員來滿足它的需要。超市經(jīng)理雇傭你來幫他解決他的問題一弛市在每天的不同時(shí)段需要不同數(shù)目的出納員(例如：午夜時(shí)只需一小批，而下午則需 要很多)來為顧客提供優(yōu)質(zhì)服務(wù)。他希望雇傭最少數(shù)目的出納員。經(jīng)理已經(jīng)提供你一天的每一小時(shí)需要出納員的最少數(shù)量一R(0), R(1), ., R(23)o R (0)表示從午夜到上午1 : 00需要出納員的最少數(shù)目

19、，R (1)表示上午1 : 00到2 : 00之間需要的，等等。每一天，這些數(shù)據(jù)都是相同的。有N人申請(qǐng)這項(xiàng)工作，每個(gè)申請(qǐng)者 I在每24小時(shí)中，從一個(gè)特定的時(shí)刻開始連續(xù)工作恰好 8小時(shí)，定義tl (0 <= tl <= 23)為上面提到的開始時(shí)刻。也就是說，如果第I個(gè)申請(qǐng)者被錄取，他(她)將從 tI時(shí)刻開始連續(xù)工作8小時(shí)。你將編寫一個(gè)程序，輸入 R (I ) (I = 0.23)和tI (I = 1.N),它們都是非負(fù)整數(shù)，計(jì)算為滿足上述限制需要雇傭的最少出納員數(shù)目。在每一時(shí)刻可以有比對(duì)應(yīng)的R (I )更多的出納員在工作。輸入輸入文件的第一行為測(cè)試點(diǎn)個(gè)數(shù)(<=20 )。每組測(cè)試

20、數(shù)據(jù)的第一行為24個(gè)整數(shù)表示R (0), R(1 ), . , R (23) (R(I ) <= 1000 )。接下來一行是 N,表示申請(qǐng)者數(shù)目(0 <= N <= 1000),接下來每行包含一個(gè)整數(shù) tI (0 <= tI <= 23)。兩組測(cè)試數(shù)據(jù)之間沒有空行。輸出對(duì)于每個(gè)測(cè)試點(diǎn)，輸出只有一行，包含一個(gè)整數(shù)，表示需要出納員的最少數(shù)目。如果無解，你應(yīng) 當(dāng)輸出“No Solution ”。樣例輸入11 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1502322110樣例輸出1我們按剛才所講到的方法對(duì)此題進(jìn)行處理。這題很容

21、易想到如下的不等式模型：設(shè)num i 為i時(shí)刻能夠開始工作的人數(shù)，x i 為實(shí)際雇傭的人數(shù)，那么 x I <=num I 設(shè)r i 為i時(shí)刻至少需要工作的人數(shù)，于是有如下關(guān)系：x I-7 +x I-6 +x I-5 +x I-4 +x I-3 +x I-2 +x I-1 +x I >=r I 設(shè) s I =x 1 +x 2 - +X得到0<=s I -s I-1 <=num I , 0<=I<=23s I -s I-8 >=r I , 8<=I<=23s 23 +s I -s I+16 >=r I , 0<=I<=7對(duì)于以

22、上的幾組不等式，我們采用一種非常笨拙的辦法處理這一系列的不等式(其實(shí)也是讓零亂的式子變得更加整齊，易于處理)。首先我們要明白差分約束系統(tǒng)的應(yīng)用對(duì)象(它通常針對(duì)多個(gè)二項(xiàng)相減的不等式的)于是我們將上面的所有式子都轉(zhuǎn)化成兩項(xiàng)未知項(xiàng)在左 邊，另外的常數(shù)項(xiàng)在右邊，且中間用>=連接的式子，即：s I -s I-1 >=0(0<=I<=23)s I-1 -s I >=-num I (0<=I<=23)s I -s I-8 >=r I (8<=I<=23)s I -s I+16 >=r I -s 23 (0<=I<= 7)這里出現(xiàn)了

23、小的困難，我們發(fā)現(xiàn)以上式子并不是標(biāo)準(zhǔn)的差分約束系統(tǒng)，因?yàn)樵谧詈笠粋€(gè)式子中出現(xiàn)了三個(gè)未知單位。但是注意到其中跟隨I變化的只有兩個(gè)，于是 s23就變得特殊起來，看來是需要我們單獨(dú)處理，于是我們把s 23 當(dāng)作已知量放在右邊。經(jīng)過這樣的整理，整個(gè)圖就很容易創(chuàng)建了， 將所有形如 A-B>=C的式子我們從節(jié)點(diǎn)B 引出一條有向邊指向 A邊的權(quán)值為C (這里注意由于左右確定，式子又是統(tǒng)一的>=的不等式，所以A和B是相對(duì)確定的，邊是一定是指向 A的)，圖就建成了 。最后枚舉所有s 23 的可能值，對(duì)于每一個(gè)s23，我們都進(jìn)行一次常規(guī)差分約束系統(tǒng)問題的求解，判斷這種情況是否可行，如果可行求出需要的最

24、優(yōu)值，記錄到Ans中，最后的Ans的值即為所求。 程序見附錄。結(jié)語：對(duì)于許多復(fù)雜的問題，我們通常選擇將不夠清晰、難以處理的模型轉(zhuǎn)化為容易理解、易于處理的模型。就像用已知的知識(shí)作為工具去探索未知領(lǐng)域一樣，聯(lián)想、發(fā)散、轉(zhuǎn)化將成為相當(dāng)有用的武器。本文選擇了差分約束系統(tǒng)這樣一個(gè)平臺(tái)，通過介紹差分約束系統(tǒng)的相關(guān)知識(shí)和其在信息學(xué)問題中的應(yīng)用以小見大，為讀者提供一個(gè)解題的思路和技巧。附錄：參考文獻(xiàn)：金牌之路競(jìng)賽解題指導(dǎo)一高中計(jì)算機(jī)王建德，周詠基«Introduction to Algorithms » H.Cormen例題信息 problem.php?pid=2008例一：ZJU2008

25、Invitation CardsTime limit: 5 Seconds Memory limit: 32768KTotal Submit: 70 Accepted Submit: 20In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have p

26、rinted invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling

27、 by bus. A special course was taken where students learned howto influence people and what is the difference between influencing and robbery.The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an

28、 hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where 'X' denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are

29、planned in such a way, that each round trip (i.e. a journey starting and finishing at the samestop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.All the ACM student members leave the CCS each morning. Each volunteer is to move t

30、o one predetermined stop to invite passengers. There are as manyvolunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of moneyto pay every day for the transport of their employees.InputThe input consists

31、 of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each descri

32、bing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCSis designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop t

33、o any other stop.OutputFor each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.Sample Input22 21 2 132 1 334 61 2 102 1 601 3 203 4 102 4 54 1 50Sample Output46210Problem Source: Central Europe 1998參考程序:constmaxn=1000000;

34、maxm=1000000;typeTedge = recordx,y,long:longint;end;waytype = array1.maxnof longint;Tdijkstra = objecth,p:array1.maxnof longint;tot:longint;procedure work(var f:waytype);end;TBellman = objectstate:array1.maxn*2of longint;procedure bellman_ford(var f:waytype); end;varindex : array0.maxnof longint;edg

35、e: array1.maxmof Tedge;BellMan: Tbellman;/ dijkstra : Tdijkstra;way1,way2 : waytype;n,m,i,ans,long,x,y,o,casen: longint;procedure qsort(fp,rp:longint);var i,j:longint;x,t:Tedge;begini:=fp;j:=rp;x:=edge(i+j)div 2;repeatwhile (edgej.x>x.x) do dec(j);while (edgei.x<x.x) do inc(i);if i<=j then

36、begint:=edgei;edgei:=edgej;edgej:=t;inc(i);dec(j);end;until i>j;if i<rp then qsort(i,rp);if fp<j then qsort(fp,j);end;procedure makeindex;var i,j:longint;beginindex0:=0;j:=1;for i:=1 to n do beginwhile (j<=m)and(edgej.x=i)do inc(j);indexi:=j-1;end;end;procedure change;var i,t : longint;b

37、eginfor i:=1 to m do begint:=edgei.x;edgei.x:=edgei.y;edgei.y:=t;end;qsort(1,m);makeindex;end;procedure Tbellman.bellman_ford(var f:waytype);var fp,rp,temp : longint;beginfp:=1;rp:=1;fillchar(f,sizeof(f),$FF);qsort(1,m);statefp:=1;f1:=0;while fp<=rp do beginfor i:=indexstatefp-1+1 to indexstatefp

38、 do begin temp:=fstatefp+edgei.long;if (temp<fedgei.y) or (fedgei.y<0) then begin inc(rp);staterp:=edgei.y;fedgei.y:=temp;end;end;inc(fp);end;end;procedure Tdijkstra.work(var f:waytype);var u,v,i,temp:longint;procedure swap(var x:longint;y:longint);var t:longint;beginphx:=y;phy:=x;t:=hx;hx:=hy

39、;hy:=t;x:=y;end;procedure up(x:longint);beginwhile x>1 doif fhx<fhx shr 1 then swap(x,x shr 1) else exit; end;procedure down(x:longint);var l,r:longint;beginwhile true do beginl:=x*2;r:=l+1;if l>tot then exit;if (l=tot)then if (fhl<fhx) then swap(x,l) else exit; if (fhx>fhl)and(fhl<

40、;fhr) then swap(x,l) else if (fhx>fhr)then swap(x,r) else exit;end;end;beginfillchar(f,sizeof(f),$FF);fillchar(p,sizeof(p),0);f1:=0;tot:=1;h1:=1;while true do beginif tot=0 then break;v:=h1;ph1:=0;h1:=htot;phtot:=1; htot:=0;dec(tot);if tot>1 then down(1);for i:=indexv-1+1 to indexv do begin te

41、mp:=fv+edgei.long;u:=edgei.y;if (fu>temp)or(fu<0) then begin fu:=temp;if pu=0 then begin inc(tot);htot:=u;pu:=tot;up(tot);end else up(pu);end;end;end;end;beginreadln(casen);for o:=1 to casen do begin readln(n,m);fillchar(edge,sizeof(edge),0);for i:=1 to m dowith edgei doreadln(x,y,long);qsort(

42、1,m);makeindex;ans:=0;bellman.bellman_ford(way1);/ dijkstra.work(way1);for i:=1 to n do inc(ans,way1i);change;bellman.bellman_ford(way2);/ dijkstra.work(way2);for i:=1 to n do inc(ans,way2i);writeln(ans);end;end.例二：ZJU1508IntervalsTime limit: 10 Seconds Memory limit: 32768KTotal Submit: 150 Accepted

43、 Submit: 49You are given n closed, integer intervals ai, bi and n integers c1, cn.Write a program that:> reads the number of intervals, their endpoints and integers c1,., cn from the standard input,> computes the minimal size of a set Z of integers which has at least ci common elements with in

44、terval ai, bi, for each i = 1,2, ., n,> writes the answer to the standard output.InputThe first line of the input contains an integer n (1 <= n <= 50 000)- the number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and

45、ci separated by single spaces and such that 0 <= ai <= bi <= 50 000 and 1 <=ci <= bi - ai + 1.Process to the end of file.OutputThe output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval ai, bi, for each i = 1, 2, ., n.Sample I

46、nput53 7 38 10 36 8 11 3 110 11 1Sample Output6Problem Source: Southwestern Europe 2002參考程序:$MODE FPC$M 0,1025$R-,Q-,S-,I-Program T_1508;TypeTEdge = Records, t, w : LongInt;End;Varedge : Array 1.50000 Of TEdge;d : Array O.50000 Of LongInt;n, i, a, b, c, max : LongInt;Procedure Bellman_Ford;Vari : Lo

47、ngInt;flag : Boolean;BeginFor i := 0 To max Do d i := 0;RepeatFlag := True;For i := 1 To n DoWith edge i DoIf (d s + w < d t ) ThenBegind t := d s + w;Flag := False;End;For i := 1 To max DoIf (d i-1 + 1 < d i ) ThenBegind i := d i-1 + 1;Flag := False;End;For i := max DownTo 1 DoIf (d i < d

48、i-1 ) ThenBegind i-1 := d i ;Flag := False;End;Until Flag;End;BeginWhile NOT EOF DoBeginReadln(n);max := 0;For i := 1 To n DoBeginReadln(a, b, c);If (b > max) Then max := b;edge i .s := b; edge i .t := a - 1; edge i .w := -c;End;Bellman_Ford;Writeln(d max - d 0 );End;End.例三：ZJU1420Cashier Employm

49、entTime limit: 10 Seconds Memory limit: 32768KTotal Submit: 34 Accepted Submit: 10A supermarket in Tehran is open 24 hours a day every day and needs a number of cashiers to fit its need. The supermarket manager has hired you to help him, solve his problem. The problem is that the supermarket needs d

50、ifferent number of cashiers at different times of each day (for example, a few cashiers after midnight, and manyin the afternoon) to provide good service to its customers, and he wants to hire the least number of cashiers for this job.The manager has provided you with the least number of cashiers ne

51、eded for every one-hour slot of the day. This data is given as R(0), R(1), ., R(23): R(0) represents the least number of cashiers needed from midnight to 1:00 A.M., R(1) shows this number for duration of 1:00 A.M. to 2:00 A.M., and so on. Note that these numbers are the same every day. There are N q

52、ualified applicants for this job. Each applicant i works non-stop once each 24 hours in a shift of exactly 8 hours starting from a specified hour, say ti (0 <= ti <= 23), exactly from the start of the hour mentioned. That is, if the ith applicant is hired, he/she will work starting from ti o&#

53、39;clock sharp for 8 hours. Cashiers do not replace one another and work exactly as scheduled, and there are enough cash registers and counters for those who are hired.You are to write a program to read the R(i)'s for i=0.23 and ti 's fori=1.N that are all, non-negative integer numbers and c

54、ompute the least number of cashiers needed to be employed to meet the mentioned constraints.Note that there can be more cashiers than the least number needed for a specific slot.InputThe first line of input is the number of test cases for this problem (atmost 20). Each test case starts with 24 integer numbers representing the R(0), R(1), .,R(23) in one line (R(i) can be at most 1000). Then thereis N, number of applicants in another line (0 <= N <= 1000)