導(dǎo)刊圖論模型的構(gòu)建

1、圖論模型的構(gòu)建1NOIP若干圖論的考題Core(2007) :圖的多源最短路算法及其簡(jiǎn)單處理雙棧排序(2008):棧的應(yīng)用+二分圖的搜索最優(yōu)貿(mào)易(2009):基本圖論2問題：求網(wǎng)線線序網(wǎng)線從機(jī)房連接到辦公室在機(jī)房，所有網(wǎng)線從左到右編號(hào)為1,2,3,N 給出每?jī)蓷l線是否交叉的信息，請(qǐng)計(jì)算辦公室內(nèi)從左到右各條線的編號(hào) 3選址問題 現(xiàn)準(zhǔn)備在 n 個(gè)居民點(diǎn)v1, v2, , vn中設(shè)置一銀行.問設(shè)在哪個(gè)點(diǎn),可使最大服務(wù)距離最小? 若設(shè)置兩個(gè)銀行,問設(shè)在哪兩個(gè)點(diǎn)?模型假設(shè) 假設(shè)各個(gè)居民點(diǎn)都有條件設(shè)置銀行,并有路相連,且路長(zhǎng)已知.4模型建立與求解用Floyd算法求出任意兩個(gè)居民點(diǎn)vi , vj 之間的最短

2、距離,并用dij 表示. 設(shè)置一個(gè)銀行,銀行設(shè)在 vi 點(diǎn)的最大服務(wù)距離為求k,使 即若設(shè)置一個(gè)銀行,則銀行設(shè)在 vk 點(diǎn),可使最大服務(wù)距離最小. 設(shè)置兩個(gè)銀行,假設(shè)銀行設(shè)在vs , vt 點(diǎn)使最大服務(wù)距離最小.記則s,t 滿足：進(jìn)一步,若設(shè)置多個(gè)銀行呢？5求k,使 即若設(shè)置一個(gè)銀行,則銀行設(shè)在 vk 點(diǎn),可使最大服務(wù)距離最小. 設(shè)置兩個(gè)銀行,假設(shè)銀行設(shè)在vs , vt 點(diǎn)使最大服務(wù)距離最小.記則s,t 滿足：進(jìn)一步,若設(shè)置多個(gè)銀行呢？6最優(yōu)貿(mào)易某國(guó)有M個(gè)城市N條道路，任意兩個(gè)城市有道路，有一部分道路為單行線，一部分為雙向道路。某人去該國(guó)旅游，從城市1出發(fā)到城市n結(jié)束，他想做水晶球的生意一次掙

3、點(diǎn)旅行費(fèi)用，每個(gè)城市有一個(gè)水晶球的價(jià)格（買入賣出都一樣），他可以經(jīng)過每個(gè)城市多次。問他能掙最多的費(fèi)用為多少？如下圖，假設(shè)城市15的價(jià)格為4，3，5，6，1則選擇1-4-5-4-5路線，掙得57分析這是一道非常典型的圖論題, 如果有扎實(shí)的圖論基礎(chǔ)解決起來并不困難.解決這道題的關(guān)鍵是發(fā)現(xiàn), 我們可以將原圖中的任意一個(gè)強(qiáng)連通分量收縮為一個(gè)點(diǎn), 這個(gè)新點(diǎn)的買入價(jià)格等于該強(qiáng)連通分量中最小的買入價(jià)格, 這個(gè)新點(diǎn)的賣出價(jià)格等于該強(qiáng)連通分量中最大的賣出價(jià)格. 這是因?yàn)? 這個(gè)新點(diǎn)的性質(zhì)和一個(gè)強(qiáng)連通分量是一樣的, 如果我們要在一個(gè)強(qiáng)連通分量中進(jìn)行購(gòu)買操作, 一定會(huì)選擇買入價(jià)格最小的那個(gè)點(diǎn), 如果我們要在一個(gè)強(qiáng)連

4、通分量中進(jìn)行賣出操作, 也一定會(huì)選擇賣出價(jià)格最大的那個(gè)點(diǎn).8分析所以算法就非常清晰了. 首先利用DFS將所有的強(qiáng)連通分量收縮, 這樣我們就可以得到一個(gè)有向無環(huán)圖G. 由于G中沒有環(huán), 我們可以對(duì)G進(jìn)行拓?fù)渑判? 然后利用遞推求得到達(dá)某個(gè)點(diǎn)i時(shí), 可能的最低買入價(jià)格best(i)是多少, 以及該點(diǎn)最終能否到達(dá)終點(diǎn). 最后對(duì)于所有能夠到達(dá)終點(diǎn)的點(diǎn)p, 設(shè)其賣出價(jià)格為sell(p), 在sell(p)-best(p)中取最大值即得到答案. 時(shí)間復(fù)雜度僅為O(V+E).在實(shí)現(xiàn)的時(shí)候最好使用棧消除DFS中的遞歸調(diào)用, 因?yàn)閳D中的點(diǎn)可以達(dá)到100000, 當(dāng)遞歸深度達(dá)到這么大的時(shí)候有相當(dāng)大的幾率發(fā)生棧溢出

5、. 參考實(shí)現(xiàn)中采用了非遞歸實(shí)現(xiàn)DFS.9奇怪的電梯大樓的每一層樓都可以停電梯，而且第i層樓(1=i=N)上有一個(gè)數(shù)字Ki(0=Ki=N)。電梯只有四個(gè)按鈕：開，關(guān)，上，下。上下的層數(shù)等于當(dāng)前樓層上的那個(gè)數(shù)字。當(dāng)然，如果不能滿足要求，相應(yīng)的按鈕就會(huì)失靈。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,)，從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因?yàn)闆]有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？輸入：二行，第一行為三個(gè)用空格隔開的正整數(shù)，表示N,A,B(1N200, 1A,BN)，第二行為N個(gè)用空格隔開的正整數(shù)，表示Ki。輸出：僅一行，即最少按鍵次數(shù),若無法到達(dá)，

6、則輸出-1。10構(gòu)圖LIFT.IN5 1 53 3 1 2 5LIFT.OUT3對(duì)于A樓而言，實(shí)際上對(duì)它最多只能做2個(gè)操作，上到A+X層或下到A-X層，當(dāng)然前提是存在A+X或A-X層。顯然，如果把每一層樓看做一個(gè)頂點(diǎn)，如果A樓可以到B樓，則從頂點(diǎn)A引一條到頂點(diǎn)B的邊，這樣一來，問題就變成了圖論中的兩頂點(diǎn)間最短路徑問題了！當(dāng)然權(quán)設(shè)為1就行了。11人穿柱子游戲在一個(gè)無限長(zhǎng)的條形路上，有n(n=200)個(gè)柱子，體積不計(jì)，有一個(gè)人想從左邊走到右邊，人近似看成一個(gè)半徑為R的圓（如下圖），問能否實(shí)現(xiàn)？12構(gòu)圖每個(gè)圓的大小完全相同，不存在包含，相切（如果內(nèi)切，就是重合了，如果外切，就是中間不連通的）等等復(fù)雜

7、的關(guān)系，只有相交和相離的關(guān)系，而且如果2個(gè)圓之間相交的話，那么這2個(gè)圓就是相通的，可以在這2個(gè)圓的圓心之間連一條邊，增加一個(gè)源點(diǎn)，與上邊有交點(diǎn)的圓和源點(diǎn)連一條邊，增加一個(gè)匯點(diǎn)，與下邊有交點(diǎn)的圓和匯點(diǎn)連一條邊，這樣就把一道幾何題完全轉(zhuǎn)換成了一道圖論題，只要判斷源點(diǎn)和匯點(diǎn)之間是否有路就可以了13奇怪的數(shù)列編程輸入3個(gè)整數(shù)n，p，q，尋找一個(gè)由整數(shù)組成的數(shù)列（a1，a2，an），要求：其中任意連續(xù)p項(xiàng)之和為正數(shù)，任意連續(xù)q項(xiàng)之和為負(fù)數(shù)。0n100，0p，qn，若不存在這樣的整數(shù)數(shù)列，則輸出NO；否則輸出滿足條件的一個(gè)數(shù)列即可。輸入格式：僅一行分別表示n，p，q，之間用一個(gè)空格隔開。輸出格式： 只有一

8、行，有解即輸出這個(gè)數(shù)列，每個(gè)數(shù)之間用一個(gè)空格隔開。否則輸出NO。14分析如果我們按常規(guī)思想，直接將第i個(gè)整數(shù)ai開始的k個(gè)整數(shù)之和描述成多項(xiàng)式ai+ai+1+ai+k-1的話，問題就很難再往下思考和解決了。所以，我們不防換個(gè)角度，暫且撇去每一項(xiàng)數(shù)究竟為何值的具體細(xì)節(jié)，而將注意力集中至連續(xù)性這一特點(diǎn)上。設(shè)si表示數(shù)列前i個(gè)整數(shù)之和，即si=a1+a2+ai。其中s0=0 (0in)。顯然根據(jù)題意，有： sisi+p (0in-p) si+qsj(0i，jn)，則從si往sj引出一條有向邊。15構(gòu)圖對(duì)于n=6，p=5，q=3的情況，我們可以建立下圖：16 對(duì)圖進(jìn)行拓?fù)渑判颍?if 圖有回路 the

9、n 無解退出 else 生成拓?fù)湫蛄衞rder0ordern；那么如果得到了一個(gè)拓?fù)湫蛄?，該如何轉(zhuǎn)換成s數(shù)組呢？因?yàn)橥負(fù)湫蛄兄许旤c(diǎn)對(duì)應(yīng)的s值是遞減的，其中s0=0。如果orderi=0，則依次設(shè)定sorder0=i，sorder1=i-1，sorderi-1=1，sorderi=0，sorderi+1=-1，sordern=i-n。例如，對(duì)于上圖所示的有向圖，可以得到下表：所以，得到s0=0，s1=-3，s2=2，s3=-1，s4=-4，s5=1，s6=-2。再根據(jù)s的定義，由： ai=(a0+a1+ai-1+ai) - (a0+a1+ai-1)=si-si-1 ，求出：a1=s1-s0=-3

10、，a2=s2-s1=5，a3=s3-s2=-3，a4=s4-s3=-3，a5=s5-s4=5，a6=s6-s5=-3。顯然這個(gè)整數(shù)數(shù)列的任意連續(xù)個(gè)整數(shù)之和為正，任意連續(xù)個(gè)整數(shù)之和為負(fù)。17牧場(chǎng)規(guī)劃小可可的好朋友Sealock最喜歡吃花生了，于是借用了小可可的牧場(chǎng)從事花生選種試驗(yàn)。他以網(wǎng)格的方式，非常規(guī)整地把牧場(chǎng)分割成M*N個(gè)矩形區(qū)域(M*N5000)，由于各個(gè)區(qū)域中地水面、沼澤面積各不相同，因此各區(qū)域地實(shí)際可種植面積也各不相同，已知區(qū)域(i,j)地可種面積使A(i,j)。每個(gè)區(qū)域種最多只能種植一個(gè)品種地花生?？煞N植面積為零地區(qū)域不能被選擇用來從事選種試驗(yàn)，同時(shí)為了防止花粉傳播到相鄰區(qū)域造成試驗(yàn)

11、結(jié)果不正確，任何兩個(gè)相鄰的區(qū)域都不可以同時(shí)種植花生。這里說的相鄰指的是兩個(gè)區(qū)域有公共邊，僅僅有公共點(diǎn)的兩個(gè)區(qū)域不算做相鄰。小可可準(zhǔn)備幫助Sealock規(guī)劃一下如何選擇種植區(qū)域，才能使得實(shí)際可種植面積總和最大。18構(gòu)圖將試驗(yàn)田轉(zhuǎn)化為點(diǎn)、并連接相鄰的試驗(yàn)田后可以發(fā)現(xiàn)，我們得到的是一個(gè)二分圖。通過對(duì)原圖的黑白染色，可以把其中的一部分稱為白點(diǎn)、另一部分稱為黑點(diǎn)。由二分圖建立網(wǎng)絡(luò)：加入源點(diǎn)和匯點(diǎn)，從源點(diǎn)向每個(gè)白點(diǎn)引一條邊，容量為白點(diǎn)對(duì)應(yīng)試驗(yàn)田的面積；從每個(gè)黑點(diǎn)向匯點(diǎn)引邊，容量為該黑點(diǎn)的對(duì)應(yīng)面積。最后將相鄰點(diǎn)之間的邊改為網(wǎng)絡(luò)中的邊，由白點(diǎn)指向黑點(diǎn)，容量為正無窮。通過求網(wǎng)絡(luò)最大流得到它的最小割，即為最優(yōu)方案

12、。S T圖1 建立網(wǎng)絡(luò)19和平委員會(huì)（SPO）要選一個(gè)委員會(huì)，但是出現(xiàn)了一個(gè)問題，某些代表是有矛盾的，不能同時(shí)選到委員會(huì)里來?，F(xiàn)在有n個(gè)政黨，每個(gè)政黨只有兩個(gè)代表，要從每個(gè)政黨中選擇一個(gè)代表，使委員會(huì)里的人都是友好的。所有的人用1到2n來編號(hào)，2i-1 和 2i屬于同一個(gè)政黨。讀入政黨總數(shù)，以及不友好的人的對(duì)數(shù)。計(jì)算是否可以建立委員會(huì)。如果可以，給出方案。輸入：第一行有兩個(gè)整數(shù)n和m，1=n=8000，0=m=20000。分別表示政黨的總數(shù)以及不友好的關(guān)系數(shù)。接下來的m行，每行整數(shù)a 和 b, 1=ab=2n，表示這兩個(gè)人是有矛盾的。輸出：無解則輸出NIE。否則打印n行，從小到大輸出你的方案中

13、各人的編號(hào)。任意可行解都是可以的。20分析：原題可描述為： 有n個(gè)組，第i個(gè)組里有兩個(gè)節(jié)點(diǎn)Ai, Ai 。需要從每個(gè)組中選出一個(gè)。而某些點(diǎn)不可以同時(shí)選出（稱之為不相容）。任務(wù)是保證選出的n個(gè)點(diǎn)都能兩兩相容。（在這里把Ai, Ai 的定義稍稍放寬一些，它們同時(shí)表示屬于同一個(gè)組的兩個(gè)節(jié)點(diǎn)。也就是說，如果我們描述Ai，那么描述這個(gè)組的另一個(gè)節(jié)點(diǎn)就可以用Ai）21初步構(gòu)圖如果Ai與Aj不相容，那么如果選擇了Ai，必須選擇Aj ；同樣，如果選擇了Aj，就必須選擇Ai 。 Ai Aj Aj Ai 這樣的兩條邊對(duì)稱我們從一個(gè)例子來看：22假設(shè)4個(gè)組，不和的代表為：1和4，2和3，7和3，那么構(gòu)圖：13245

14、678假設(shè)： 首先選13必須選，2不可選8必須選，4、7不可選5、6可以任選一個(gè)23矛盾的情況為：存在Ai，使得Ai既必須被選又不可選。 得到算法1：枚舉每一對(duì)尚未確定的Ai, Ai ，任選1個(gè)，推導(dǎo)出相關(guān)的組，若不矛盾，則可選擇；否則選另1個(gè)，同樣推導(dǎo)。若矛盾，問題必定無解。1324567824此算法正確性簡(jiǎn)要說明：由于Ai,Ai 都是尚未確定的，它們不與之前的組相關(guān)聯(lián)，前面的選擇不會(huì)影響Ai, Ai 。算法的時(shí)間復(fù)雜度在最壞的情況下為O(nm)。在這個(gè)算法中，并沒有很好的利用圖中邊的對(duì)稱性25先看這樣一個(gè)結(jié)構(gòu)： 更一般的說：在每個(gè)一個(gè)環(huán)里，任意一個(gè)點(diǎn)的選擇代表將要選擇此環(huán)里的每一個(gè)點(diǎn)。不妨

15、把環(huán)收縮成一個(gè)子節(jié)點(diǎn)（規(guī)定這樣的環(huán)是極大強(qiáng)連通子圖）。新節(jié)點(diǎn)的選擇表示選擇這個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的環(huán)中的每一個(gè)節(jié)點(diǎn)。此圖中1和3構(gòu)成一個(gè)環(huán)，這樣1和3要么都被選擇，要么都不被選。2和4同樣如此。圖的收縮1324567826對(duì)于原圖中的每條邊Ai Aj（設(shè)Ai屬于環(huán)Si，Aj屬于環(huán)Sj）如果SiSj，則在新圖中連邊： Si Sj 這樣構(gòu)造出一個(gè)新的有向無環(huán)圖。 此圖與原圖等價(jià)。13245678S1 S1S2 S2 S3 S3圖的收縮27算法2通過求強(qiáng)連通分量，可以把圖轉(zhuǎn)換成新的有向無環(huán)圖，在這個(gè)基礎(chǔ)上，介紹一個(gè)新的算法。新算法中，如果存在一對(duì)Ai, Ai屬于同一個(gè)環(huán)，則判無解，否則將采用拓?fù)渑判?，以自?/p>

16、向上的順序進(jìn)行推導(dǎo)，一定能找到可行解。28算法2的流程： 1構(gòu)圖2求圖的極大強(qiáng)連通子圖3把每個(gè)子圖收縮成單個(gè)節(jié)點(diǎn)，根據(jù)原圖關(guān)系構(gòu)造一個(gè)有向無環(huán)圖4判斷是否有解，無解則輸出（退出）5對(duì)新圖進(jìn)行拓?fù)渑判?自底向上進(jìn)行選擇、刪除7輸出29瘦陀陀和胖陀陀一場(chǎng)可怕的戰(zhàn)爭(zhēng)后，瘦陀陀和他的好朋友胖陀陀將要?jiǎng)P旋。瘦陀陀處在城市A胖陀陀處在另外一個(gè)未知的城市他們打算選一個(gè)城市X（這個(gè)由瘦陀陀來決定）胖陀陀會(huì)趕在瘦陀陀之前到達(dá)城市X然后等待瘦陀陀也趕到城市X與他匯合，并舉辦一次慶祝宴會(huì)（由瘦陀陀請(qǐng)客）接著一起回到他們的家鄉(xiāng)城市B由于胖陀陀嘴饞，他要求舉辦宴會(huì)的城市必須是瘦陀陀回家的路線中舉辦宴會(huì)最貴的一個(gè)城市。

17、30一個(gè)例子（續(xù)）瘦陀陀正專注地看回家的地圖地圖上標(biāo)有n（n200）個(gè)城市和某些城市間直達(dá)的道路以及每條道路的過路費(fèi)瘦陀陀還知道在每一座城市舉辦宴會(huì)的花費(fèi)。給出地圖和A、B的位置請(qǐng)你告訴瘦陀陀回家的最小費(fèi)用你的程序會(huì)接收到多次詢問即對(duì)于每對(duì)城市(c1,c2)，你的程序應(yīng)該立刻給出瘦陀陀從c1到c2的最小花費(fèi)。 31分析胖陀陀規(guī)定必須在最貴的城市舉辦宴會(huì)因此不能簡(jiǎn)單地選擇一條最短路走若路上有一個(gè)花費(fèi)特別貴的城市對(duì)于每個(gè)點(diǎn)X，如果在那里辦宴會(huì)如何求最短路？多個(gè)詢問怎么處理？floyd計(jì)算每?jī)牲c(diǎn)的距離？SSSP就可以勝任嗎？AB = AX + XB32樹網(wǎng)的核 給出一棵無根樹，邊上有權(quán)。稱樹的最長(zhǎng)路

18、徑為直徑，定義路徑的偏心距為：點(diǎn)到路徑的上的點(diǎn)的最小值的最大值，給出一個(gè)s，找出直徑上的某段長(zhǎng)度不超過s的路徑，使得偏心距最小。33分析考慮到樹的性質(zhì)，對(duì)于任意兩點(diǎn)，最短路=聯(lián)通路=最長(zhǎng)路。首先用floyd算法求出任意兩點(diǎn)之間最短路。同時(shí)可以求出最長(zhǎng)路徑上都有哪些點(diǎn)。由于這是一棵樹，最短路必然唯一。設(shè)mida,b是a,b之間的聯(lián)通路上的一個(gè)中間點(diǎn)?？紤]問題的解，構(gòu)造一個(gè)函數(shù)F(k,a,b)為K到ab間的最短路的長(zhǎng)度。則f(k,a,b)=mindk,mida,b,fk,a,mida,b,fk,mida,b,b寫出了這個(gè)方程，便不難得出一個(gè)三次方的算法。在實(shí)際做的時(shí)候，可以把k放在最外層枚舉，這樣

19、內(nèi)層實(shí)際上只用到了f的后面2維，用2維數(shù)組記錄即可。34雙棧排序 有兩個(gè)隊(duì)列和兩個(gè)棧,分別命名為隊(duì)列1(q),隊(duì)列2(q2),棧1(s1)和棧2(s2).最初的時(shí)候,q2,s1和s2都為空,而q中有n個(gè)數(shù)(n=1000),為1n的某個(gè)排列.現(xiàn)在支持如下四種操作:a操作,將 q的首元素提取出并加入s1的棧頂.b操作,將s1的棧頂元素彈出并加入q2的隊(duì)列尾.c操作,將 q的首元素提取出并加入s2的棧頂.d操作,將s2的棧頂元素彈出并加入q2的隊(duì)列尾.請(qǐng)判斷,是否可以經(jīng)過一系列操作之后,使得q2中依次存儲(chǔ)著1,2,3,n.如果可以,求出字典序最小的一個(gè)操作序列. 35考慮單棧例1：1,2,3,4,5

20、 例2：5,4,3,2,1 例3：3,2,4,5,1 例4：3,1,4,5,2 no; yes; yes; yes;36定理定理：對(duì)于任意兩個(gè)數(shù)qi和qj來說,它們不能壓入同一個(gè)棧中的充要條件p是:存在一個(gè)k,使得ijk且qkqiq i,這顯然是不正確的.37證明必要性：也就是,如果兩個(gè)數(shù)不可以壓入同一個(gè)棧,那么它們一定滿足條件p.這里我們來證明它的逆否命題,也就是如果不滿足條件p,那么這兩個(gè)數(shù)一定可以壓入同一個(gè)棧.“不滿足條件p有兩種情況:一種是對(duì)于任意ijk且qiqi;另一種是對(duì)于任意iqj.第一種情況下,很顯然,在qk被壓入棧的時(shí)候,qi已經(jīng)被彈出棧.那么,qk不會(huì)對(duì)qj產(chǎn)生任何影響(這

21、里可能有點(diǎn)亂,因?yàn)榭雌饋?當(dāng)qjqK的時(shí)候,是會(huì)有影響的,但實(shí)際上,這還需要另一個(gè)數(shù)R,滿足JKR且 qrqjqk,也就是證明充分性的時(shí)候所說的情況而事實(shí)上我們現(xiàn)在并不考慮這個(gè)r,所以說qk對(duì)qj沒有影響).第二種情況下,我們可以發(fā)現(xiàn)這其實(shí)就是一個(gè)降序序列,所以所有數(shù)字都可以壓入同一個(gè)棧.這樣,原命題的逆否命題得證,所以原命題得證.此時(shí),條件p為qi和qj不能壓入同一個(gè)棧的充要條件也得證.38構(gòu)圖這樣,我們對(duì)所有的數(shù)對(duì)(i,j)滿足1=ij=n,檢查是否存在ijk滿足qk q iq j.如果存在,那么在點(diǎn)i和點(diǎn)j之間連一條無向邊,表示q i和qj不能壓入同一個(gè)棧. 二分圖的兩部分看作兩個(gè)棧,因

22、為二分圖的同一部分內(nèi)不會(huì)出現(xiàn)任何連邊,也就相當(dāng)于不能壓入同一個(gè)棧的所有結(jié)點(diǎn)都分到了兩個(gè)棧中.此時(shí)我們只考慮檢查是否有解,所以只要O(n)檢查出這個(gè)圖是不是二分圖,就可以得知是否有解. 39深度優(yōu)先搜索求解檢查有解的問題已經(jīng)解決.接下來的問題是,如何找到字典序最小的解.實(shí)際上,可以發(fā)現(xiàn),如果把二分圖染成1和2兩種顏色,那么結(jié)點(diǎn)染色為1對(duì)應(yīng)當(dāng)前結(jié)點(diǎn)被壓入s1,為2對(duì)應(yīng)被壓入s2.為了字典序盡量小,我們希望讓編號(hào)小的結(jié)點(diǎn)優(yōu)先壓入s1.又發(fā)現(xiàn)二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取一個(gè)未染色的編號(hào)最小的結(jié)點(diǎn),將它染色為1并從它開始DFS染色,直到所有結(jié)點(diǎn)都被染色為止.這樣,我們就得

23、到了每個(gè)結(jié)點(diǎn)應(yīng)該壓入哪個(gè)棧中 。還有一點(diǎn)小問題,就是如果對(duì)于數(shù)對(duì)(i,j),都去枚舉檢查是否存在k，使得qkqI M40最優(yōu)乘車（NOI97）一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒有一路巴士可以直接到達(dá)S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺(tái)的另一路巴士, 這樣換乘幾次后到達(dá)S公園。現(xiàn)在用整數(shù)1，2， N 給H城的所有的巴士站編號(hào)，約定這名旅客所在飯店的巴士站編號(hào)為1，2， S，公園巴士站的編號(hào)為N。寫一個(gè)程序，幫助這名旅客尋找一個(gè)最優(yōu)乘車方案,使他在從飯店乘車到S公園的過程中換車的次數(shù)最少。輸入N和M條公交線路信息求最少換車的次數(shù)41模型的構(gòu)建我們來分析樣例3 76 74 7 3 62 1 3 5674736213542考察4 7 3 6這條線路。由于巴士在同一線路上行走不需換車，我們可設(shè)4 7，