數(shù)與圖完美結(jié)合—淺析差分約束系統(tǒng)

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

2、束系統(tǒng)在信息學(xué)題目中的應(yīng)用，并逐漸歸納解決這類問題的思考方向。 目錄 關(guān)鍵字 ···········································

3、83;·················································

4、83;·【2】 Bellman-ford算法 ·············································&#

5、183;······························【2】算法簡單介紹 ·················

6、3;·················································

7、3;·············【2】算法具體流程 ···································

8、·············································【2】例題一ZJU2008 ··

9、3;·················································

10、3;·························【4】 差分約束系統(tǒng) ·······················

11、;··················································

12、;···········【5】例題二ZJU1508 ····································

13、83;·········································【5】線性程序設(shè)計(jì) ·······

14、;··················································

15、;························【7】差分約束系統(tǒng) ························&

16、#183;·················································&

17、#183;······【7】例題三 ZJU1420·········································

18、;···································【8】 結(jié)語 ·············

19、3;·················································

20、3;···································【9】 附錄 ·············

21、83;·················································

22、83;···································【9】關(guān)鍵字 差分約束系統(tǒng)、不等式、單元最短路徑、轉(zhuǎn)化正文 在分析差分約束系統(tǒng)之前，我們首先介紹一個解決單元最短路徑問題的Bellman Ford算法，它的應(yīng)用十分廣泛，在差

23、分約束系統(tǒng)中更充當(dāng)著重要的角色。Bellman-ford 算法 算法簡單介紹這個算法能在更一般的情況下解決最短路的問題。何謂一般，一般在該算法下邊的權(quán)值可以為負(fù)，可以運(yùn)用該算法求有向圖的單元最長路徑或者最短路徑。我們這里僅以最短路徑為例。Bellman ford 類似于Dijkstra算法，對每一個節(jié)點(diǎn)vV，逐步減小從起點(diǎn)s到終點(diǎn)v最短路的估計(jì)量distv直到其達(dá)到真正的最短路徑值mindistv。Bellman-ford算法同時返回一個布爾值，如果不存在從源結(jié)點(diǎn)可達(dá)的負(fù)權(quán)回路，算法返回布爾值TRUE，反之返回FALSE。算法具體流程1 枚舉每條邊(u,v)E（G）。2 對枚舉到的邊進(jìn)行一次更

24、新操作。3 回到步驟1，此過程重復(fù)n-1次，以確定沒有更可以優(yōu)化的情況。4 枚舉每條邊（u，v）若仍然存在可以更新的邊，則說明有向圖中出現(xiàn)了負(fù)權(quán)回路，于是返回布爾值FALSE。5 返回布爾值TRUE。注：這里的更新操作是一種松弛技術(shù)，以單元最短路徑為例這個操作就是保證distv<=distu+wu,v，即if distv>distu+wu,v then distv=distu+wu,v，如果是最長路徑則是保證distv>=distu+wu,v。定義一個有向圖G=（V，E），w（u，v）表示由結(jié)點(diǎn)u到v的邊的權(quán)值。偽代碼如下：For i=1 to |V|G|-1 Do for

25、每條邊(u，v)E|G| Do 更新操作（u，v，w（u，v）For 每條邊（u，v）E|G| Do if 仍然有可更新內(nèi)容 then return FalseReturn True6MAX7MAX06785-2-4-3792STMAXMAXMAXMAX06785-2-4-3792ST下圖描述了該算法的操作過程，粗線條代表已更新線段247-206785-2-4-3792ST247206785-2-4-3792ST647206785-2-4-3792ST圖例中，S為源節(jié)點(diǎn)，粗線斷覆蓋的邊表示最近一次執(zhí)行更新操作的邊。算法執(zhí)行|V|-1次操作，每次操作都對所有可以進(jìn)行松弛操作的邊進(jìn)行擴(kuò)展。證明一下

26、Bellman-Ford算法的正確性。1設(shè)G=（V，E）為有向加權(quán)圖，源節(jié)點(diǎn)為S，加權(quán)函數(shù)為w：E-R。如果有負(fù)權(quán)回路則Bellman_ford算法一定會返回布爾值false,否則返回TRUE。證明略。2設(shè)G=（V，E）為有向加權(quán)圖，源節(jié)點(diǎn)為S加權(quán)函數(shù)為w：E-R，并且G不含從s可達(dá)的負(fù)權(quán)回路，則算法Bellman_ford終止時，對所有從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)槁窂絧是簡單路徑，所以k<=|V|-1。我們希望通過歸納證明對i=0,1,k，在

27、對G的邊進(jìn)行完第i趟操作后有dvi=mindist(s,vi),且該等式此后一直保持成立，因?yàn)榭偣灿衸V|-1次操作，所以上述結(jié)論證明命題成立。我們發(fā)現(xiàn)與Dijkstra不同，Bellman ford更多的是對邊進(jìn)行操作，在稀疏圖，即點(diǎn)多邊少的圖中，用Bellman Ford更能高效的解決單元最短路徑問題。下面一道例題來進(jìn)一步熟悉Bellman Ford并與Dijkstra作一下簡單的時間上的比較。例題一：ZJU2008 Invitation Cards題目大意在有向加權(quán)圖中G（V，E），郵局要從起點(diǎn)S向其他n個節(jié)點(diǎn)發(fā)送郵件，于是派出n個郵遞員，分別到達(dá)其他n個地點(diǎn)發(fā)送，然后回到起點(diǎn)S，求出所

28、有郵遞員所經(jīng)過的總路程的最小值。數(shù)據(jù)范圍 1 <= P,Q <= 1000000。P表示節(jié)點(diǎn)數(shù)目，Q表示邊的個數(shù)。題目分析這道題算法很簡單，即求出從s到任意點(diǎn)的最短路徑，求其和ANS1，再將所有有向邊反向（這個過程將求從另外n個結(jié)點(diǎn)到s的最短路徑轉(zhuǎn)化為從s到其他n個點(diǎn)的最短路徑），再求一次s到任意點(diǎn)的最短路徑，求其和ANS2，Ans=Ans1+Ans2即為所求。但是，此題難在數(shù)據(jù)量上，無論是Dijkstra的O() 的算法，還是Bellmanford的O(VE)的算法都無法在數(shù)據(jù)規(guī)模最大的情況下在5s的時間內(nèi)得出結(jié)果，于是需要做出一點(diǎn)優(yōu)化。關(guān)于Dijkstra的優(yōu)化：用堆維護(hù)使尋找

29、需要擴(kuò)展的點(diǎn)的過程復(fù)雜度降低為1。復(fù)雜度大幅降低。關(guān)于Bellman ford的優(yōu)化：可以將Bellman ford需要擴(kuò)展的點(diǎn)放進(jìn)隊(duì)列中，擴(kuò)展順序有了新的變化。用一個隊(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 Dijkstr

30、a&Heap在ZJU Online Judge中進(jìn)行評測結(jié)果如下：算法運(yùn)行所有數(shù)據(jù)所用時間Dijkstra5s （TLE）Bellman Ford 1.46sDijkstra&Heap 1.24s差分約束系統(tǒng)對于解決差分約束系統(tǒng)問題的操作過程和使用原理，我們通過下面一道簡單的題目進(jìn)行了解。引例：例題二 Zju1508 Interval 題目大意：有一個序列，題目用n個整數(shù)組合 ai,bi,ci來描述它，ai，bi，ci表示在該序列中處于ai，bi這個區(qū)間的整數(shù)至少有ci個。如果存在這樣的序列，請求出滿足題目要求的最短的序列長度是多少。如果不存在則輸出 -1。輸入：第一行包括一個

31、整數(shù)n，表示區(qū)間個數(shù)，以下n行每行描述這些區(qū)間，第i+1行三個整數(shù)ai，bi，ci，由空格隔開，其中0<=ai<=bi<=50000 而且 1<=ci<=bi-ai+1。輸出：一行，輸出滿足要求的序列的長度的最小值。淺析初看此題感覺無從下手，我們將范圍和個數(shù)進(jìn)行量化，讓問題看起來更加簡單些。將問題數(shù)字化：若記，那么本題約束條件即為 建立不等式模型：這樣的描述使一個約束條件所牽涉的變量太多，不妨設(shè) (i=1,2,n)約束條件即可用以下不等式表示： 值得注意的是，這樣定義的S若僅僅滿足約束條件的要求是不能完整體現(xiàn)它的意義的，S中的各個組成之間并不是相對獨(dú)立的，他們存在

32、著聯(lián)系。由于，且t要么為1，要么為0，則一定比大 ，且至多大1。于是有：那么如何找到滿足要求的這樣一組S，且使其個數(shù)最少呢？這里我們看到最少就會聯(lián)想到貪心，確實(shí)這道題目用貪心可行，且不失為一種很好的做法，但在這里我們不作多的介紹。我們將針對這個不等式組進(jìn)行聯(lián)想，遷移。注意到不等式中只涉及到了2個未知數(shù)，用減號相連接。這樣的式子是否與過去曾經(jīng)學(xué)過的Bellmanford中的松弛操作所達(dá)到的效果相類似呢？聯(lián)想：我們需要尋找一個滿足以下要求的S數(shù)組而Bellman-Ford 每次的更新操作為即在經(jīng)過若干次更新操作將要保證 dv<=du+wu,v這里我們也有一個已知量-邊的權(quán)值，即wu,v，于是

33、整理一下得du-dv>=wu,v經(jīng)過這樣的變形，不難看出，兩個式子有著極為驚人的相似！于是做出如下的轉(zhuǎn)化：1 我們將，看作n+1個點(diǎn)。2 若和之間有著約束關(guān)系，例如Si-1-Si>= -1,那么我們從結(jié)點(diǎn) 向結(jié)點(diǎn)連上一條有向邊，邊的權(quán)值為-1。這樣如果我們從出發(fā)，求出結(jié)點(diǎn)到的最短路徑，則為滿足要求情況下的最小值。相反如果我們發(fā)現(xiàn)在Bellmanford算法執(zhí)行的過程中存在有負(fù)權(quán)回路，則說明不存在滿足要求的式子。于是通過合理地建立數(shù)學(xué)模型，將不等式圖形化，用Bellmanford作為武器，最終此題得到了圓滿的解決！思考：本題只要求輸出最少的個數(shù)，那么能否通過上述方法構(gòu)造出相應(yīng)的數(shù)列呢

34、？答案是肯定的。其實(shí)在Bellmanford的過程中，我們已經(jīng)得到了所有結(jié)點(diǎn)上S的值，那么由求出所有T，當(dāng)為1則輸出i，即可輸出滿足題目要求的序列?？偨Y(jié)：對于ZJU1508的問題，最終可以化為一類線性不等式定義的線性函數(shù)。而這類問題其實(shí)是可以轉(zhuǎn)化為單元最短路徑問題，從而用剛才所準(zhǔn)備到的Bellman Ford算法來解決它。線性程序設(shè)計(jì)：我們?yōu)榫€性程序設(shè)計(jì)問題制定一個嚴(yán)格的數(shù)學(xué)描述：給定一個m*n矩陣A，維向量b和維向量c，我們希望找出由n個元素組成的向量x，在由Ax<=b所給出的m個約束條件下，使目標(biāo)函數(shù)達(dá)到最大值。其實(shí)很多問題都可以通過這樣一個線性程序設(shè)計(jì)框架來進(jìn)行描述。在實(shí)際的問題中

35、，也經(jīng)常要對其進(jìn)行分析和解決。上述例題使我們對這一類線性程序設(shè)計(jì)問題提供了一個多項(xiàng)式時間的算法。它將一類特殊的線性不等式與圖論緊密聯(lián)系在了一起。這類特殊的線性不等式，我們稱它為差分約束系統(tǒng)，它是可以用單元最短路徑來求解的。差分約束系統(tǒng)：差分約束系統(tǒng)是一個線性程序設(shè)計(jì)中特殊的一種，線性程序設(shè)計(jì)中矩陣A的每一行包含一個1和一個-1，A的所有其他元素均為0。由Ax<=b給出的約束條件形成m個差分約束的集合，其中包含n個未知單元。每個約束條件均可夠成簡單的不等式如下：（1<=I,j<=n,1<=k<=m）簡單舉例：找出未知量,并且滿足以下差分約束條件：需要注意的是，用Be

36、llmanford求出的具體答案只是眾多答案中的一種，答案并不唯一，但答案之間卻也有著聯(lián)系。這里我們并不對其進(jìn)行專門的探討。了解了差分約束系統(tǒng)的整個過程，下面再看另外一道題目，讓我們對差分約束系統(tǒng)的應(yīng)用能夠有更加深刻的認(rèn)識。例題三 zju1420 Cashier Employment 出納員問題題目中文翻譯： Tehran的一家每天24小時營業(yè)的超市，需要一批出納員來滿足它的需要。超市經(jīng)理雇傭你來幫他解決他的問題超市在每天的不同時段需要不同數(shù)目的出納員（例如：午夜時只需一小批，而下午則需要很多）來為顧客提供優(yōu)質(zhì)服務(wù)。他希望雇傭最少數(shù)目的出納員。 經(jīng)理已經(jīng)提供你一天的每一小時需要出納員的最少數(shù)量

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

38、在工作。 輸入 輸入文件的第一行為測試點(diǎn)個數(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ù)之間沒有空行。 輸出 對于每個測試點(diǎn)，輸出只有一行，包含一個整數(shù)，表示需要出納員的最少數(shù)目。如果無解，你應(yīng)當(dāng)輸出“No Solution”。 樣例輸入 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 5 0 23 2

39、2 1 10 樣例輸出 1我們按剛才所講到的方法對此題進(jìn)行處理。這題很容易想到如下的不等式模型： 設(shè)num i 為i時刻能夠開始工作的人數(shù)，x i 為實(shí)際雇傭的人數(shù)，那么x I <=num I 。 設(shè)r i 為i時刻至少需要工作的人數(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 I ，得到 0<=s I -s I-1 <=num I ， 0<=I<=23 s I -s I-8 >=r I ， 8<=I<=23 s

40、23 +s I -s I+16 >=r I ， 0<=I<=7 對于以上的幾組不等式，我們采用一種非常笨拙的辦法處理這一系列的不等式(其實(shí)也是讓零亂的式子變得更加整齊，易于處理)。首先我們要明白差分約束系統(tǒng)的應(yīng)用對象（它通常針對多個二項(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

41、>=-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)了小的困難，我們發(fā)現(xiàn)以上式子并不是標(biāo)準(zhǔn)的差分約束系統(tǒng)，因?yàn)樵谧詈笠粋€式子中出現(xiàn)了三個未知單位。但是注意到其中跟隨 I變化的只有兩個，于是s23就變得特殊起來，看來是需要我們單獨(dú)處理，于是我們把

42、 s 23 當(dāng)作已知量放在右邊。經(jīng)過這樣的整理，整個圖就很容易創(chuàng)建了，將所有形如 A-B>=C 的式子 我們從節(jié)點(diǎn)B 引出一條有向邊指向 A  邊的權(quán)值為C  （這里注意由于左右確定，式子又是統(tǒng)一的>=的不等式，所以A和B是相對確定的，邊是一定是指向A的） ，圖就建成了 。 最后枚舉所有s 23 的可能值，對于每一個s23，我們都進(jìn)行一次常規(guī)差分約束系統(tǒng)問題的求解，判斷這種情況是否可行，如果可行求出需要的最優(yōu)值，記錄到Ans中，最后的Ans的值即為所求。 程序見附錄。結(jié)語：對于許多復(fù)雜的問題，我們通常選擇將不夠清晰、難以處理的模型轉(zhuǎn)化為容易理解、易于處理的模型。

43、就像用已知的知識作為工具去探索未知領(lǐng)域一樣，聯(lián)想、發(fā)散、轉(zhuǎn)化將成為相當(dāng)有用的武器。本文選擇了差分約束系統(tǒng)這樣一個平臺，通過介紹差分約束系統(tǒng)的相關(guān)知識和其在信息學(xué)問題中的應(yīng)用以小見大，為讀者提供一個解題的思路和技巧。附錄：參考文獻(xiàn)：金牌之路競賽解題指導(dǎo)高中計(jì)算機(jī) 王建德，周詠基 Introduction to Algorithms H.Cormen例題信息 例一：ZJU2008Invitation CardsTime limit: 5 Seconds   Memory limit: 32768K   Total Submit: 70  

44、 Accepted Submit: 20   In 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 printed invitation cards with all the necessary information an

45、d 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 by bus. A special course was taken where students learned ho

46、w to 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 hour. After reaching the destination stop they return empt

47、y 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 planned in such a way, that each round trip (i.e. a journey

48、 starting and finishing at the same stop) 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 to one predetermined stop to invite passengers. There are

49、as many volunteers 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 money to pay every day for the transport of their employees. InputThe input consists of N cases. The first line of the input contains only

50、 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 describing one bus line. Each of the lines contains exactly

51、three numbers - the originating stop, the destination stop and the price. The CCS is 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 to any other stop. OutputFor each case, print one line

52、 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 參考程序：const maxn=1000000; maxm=1000000;type Tedge = record x,y,long:longin

53、t; end; waytype = array1.maxnof longint; Tdijkstra = object h,p:array1.maxnof longint; tot:longint; procedure work(var f:waytype); end; TBellman = object state:array1.maxn*2of longint; procedure bellman_ford(var f:waytype); end;var index : array0.maxnof longint; edge : array1.maxmof Tedge; BellMan :

54、 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; begin i:=fp;j:=rp;x:=edge(i+j)div 2; repeat while (edgej.x>x.x) do dec(j); while (edgei.x<x.x) do inc(i); if i<=j then begin t:=edgei;ed

55、gei:=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; begin index0:=0;j:=1; for i:=1 to n do begin while (j<=m)and(edgej.x=i)do inc(j); indexi:=j-1; end; end;procedure change; var i,t : longint; b

56、egin for i:=1 to m do begin t:=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; begin fp:=1;rp:=1; fillchar(f,sizeof(f),$FF); qsort(1,m); statefp:=1;f1:=0; while fp<=rp do begin for i:=indexstatefp-1+1 t

57、o indexstatefp 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; begin

58、 phx:=y;phy:=x; t:=hx;hx:=hy;hy:=t; x:=y; end; procedure up(x:longint); begin while x>1 do if fhx<fhx shr 1 then swap(x,x shr 1) else exit; end; procedure down(x:longint); var l,r:longint; begin while true do begin l:=x*2;r:=l+1; if l>tot then exit; if (l=tot)then if (fhl<fhx) then swap(

59、x,l) else exit; if (fhx>fhl)and(fhl<fhr) then swap(x,l) else if (fhx>fhr)then swap(x,r) else exit; end; end; begin fillchar(f,sizeof(f),$FF); fillchar(p,sizeof(p),0); f1:=0;tot:=1;h1:=1; while true do begin if tot=0 then break; v:=h1;ph1:=0;h1:=htot;phtot:=1; htot:=0;dec(tot); if tot>1 t

60、hen down(1); for i:=indexv-1+1 to indexv do begin temp:=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;begin readln(casen); for o:=1 to casen do begin readln(n,m); fillchar(edge,siz

61、eof(edge),0); for i:=1 to m do with edgei do readln(x,y,long); qsort(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.例二：ZJU1508In

62、tervalsTime limit: 10 Seconds   Memory limit: 32768K   Total Submit: 150   Accepted Submit: 49   You 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,

63、 ., cn from the standard input,> computes the minimal size of a set Z of integers which has at least ci common elements with interval 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

64、 number of intervals. The following n lines describe the intervals. The i+1-th line of the input contains three integers ai, bi and 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 exact

65、ly 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 Input53 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; Type TEdge = Record s, t,

66、 w : LongInt; End; Var edge : Array 1.50000 Of TEdge; d : Array 0.50000 Of LongInt; n, i, a, b, c, max : LongInt; Procedure Bellman_Ford; Var i : LongInt; flag : Boolean; Begin For i := 0 To max Do d i := 0; Repeat Flag := True; For i := 1 To n Do With edge i Do If (d s + w < d t ) Then Begin d t

67、 := d s + w; Flag := False; End; For i := 1 To max Do If (d i-1 + 1 < d i ) Then Begin d i := d i-1 + 1; Flag := False; End; For i := max DownTo 1 Do If (d i < d i-1 ) Then Begin d i-1 := d i ; Flag := False; End; Until Flag; End; Begin While NOT EOF Do Begin Readln(n); max := 0; For i := 1 To

68、 n Do Begin Readln(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 EmploymentTime limit: 10 Seconds   Memory limit: 32768K   Total Submit: 34   Accepted Submit: 10   A supermarket in Tehran is