導刊圖論模型的構建

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

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

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

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

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

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

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

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

9、n 無解退出 else 生成拓撲序列order0ordern；那么如果得到了一個拓撲序列，該如何轉換成s數(shù)組呢？因為拓撲序列中頂點對應的s值是遞減的，其中s0=0。如果orderi=0，則依次設定sorder0=i，sorder1=i-1，sorderi-1=1，sorderi=0，sorderi+1=-1，sordern=i-n。例如，對于上圖所示的有向圖，可以得到下表：所以，得到s0=0，s1=-3，s2=2，s3=-1，s4=-4，s5=1，s6=-2。再根據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。顯然這個整數(shù)數(shù)列的任意連續(xù)個整數(shù)之和為正，任意連續(xù)個整數(shù)之和為負。17牧場規(guī)劃小可可的好朋友Sealock最喜歡吃花生了，于是借用了小可可的牧場從事花生選種試驗。他以網格的方式，非常規(guī)整地把牧場分割成M*N個矩形區(qū)域(M*N5000)，由于各個區(qū)域中地水面、沼澤面積各不相同，因此各區(qū)域地實際可種植面積也各不相同，已知區(qū)域(i,j)地可種面積使A(i,j)。每個區(qū)域種最多只能種植一個品種地花生?？煞N植面積為零地區(qū)域不能被選擇用來從事選種試驗，同時為了防止花粉傳播到相鄰區(qū)域造成試驗

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

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

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

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

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

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

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

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

19、內層實際上只用到了f的后面2維，用2維數(shù)組記錄即可。34雙棧排序 有兩個隊列和兩個棧,分別命名為隊列1(q),隊列2(q2),棧1(s1)和棧2(s2).最初的時候,q2,s1和s2都為空,而q中有n個數(shù)(n=1000),為1n的某個排列.現(xiàn)在支持如下四種操作:a操作,將 q的首元素提取出并加入s1的棧頂.b操作,將s1的棧頂元素彈出并加入q2的隊列尾.c操作,將 q的首元素提取出并加入s2的棧頂.d操作,將s2的棧頂元素彈出并加入q2的隊列尾.請判斷,是否可以經過一系列操作之后,使得q2中依次存儲著1,2,3,n.如果可以,求出字典序最小的一個操作序列. 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定理定理：對于任意兩個數(shù)qi和qj來說,它們不能壓入同一個棧中的充要條件p是:存在一個k,使得ijk且qkqiq i,這顯然是不正確的.37證明必要性：也就是,如果兩個數(shù)不可以壓入同一個棧,那么它們一定滿足條件p.這里我們來證明它的逆否命題,也就是如果不滿足條件p,那么這兩個數(shù)一定可以壓入同一個棧.“不滿足條件p有兩種情況:一種是對于任意ijk且qiqi;另一種是對于任意iqj.第一種情況下,很顯然,在qk被壓入棧的時候,qi已經被彈出棧.那么,qk不會對qj產生任何影響(這

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

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

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