圖論模型的構(gòu)建

圖論模型的構(gòu)建第一頁，共四十七頁，編輯于2023年，星期二NOIP若干圖論的考題Core(2007)

:圖的多源最短路算法及其簡(jiǎn)單處理雙棧排序(2008):棧的應(yīng)用+二分圖的搜索最優(yōu)貿(mào)易(2009):基本圖論第二頁，共四十七頁，編輯于2023年，星期二問題：求網(wǎng)線線序網(wǎng)線從機(jī)房連接到辦公室在機(jī)房，所有網(wǎng)線從左到右編號(hào)為1,2,3,…,N

給出每?jī)蓷l線是否交叉的信息，請(qǐng)計(jì)算辦公室內(nèi)從左到右各條線的編號(hào)第三頁，共四十七頁，編輯于2023年，星期二選址問題現(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)已知.第四頁，共四十七頁，編輯于2023年，星期二模型建立與求解用Floyd算法求出任意兩個(gè)居民點(diǎn)vi,vj之間的最短距離,并用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è)銀行呢？第五頁，共四十七頁，編輯于2023年，星期二求k,使

即若設(shè)置一個(gè)銀行,則銀行設(shè)在

vk點(diǎn),可使最大服務(wù)距離最小.⑵設(shè)置兩個(gè)銀行,假設(shè)銀行設(shè)在vs,vt點(diǎn)使最大服務(wù)距離最小.記則s,t滿足：進(jìn)一步,若設(shè)置多個(gè)銀行呢？第六頁，共四十七頁，編輯于2023年，星期二最優(yōu)貿(mào)易某國(guó)有M個(gè)城市N條道路，任意兩個(gè)城市有道路，有一部分道路為單行線，一部分為雙向道路。某人去該國(guó)旅游，從城市1出發(fā)到城市n結(jié)束，他想做水晶球的生意一次掙點(diǎn)旅行費(fèi)用，每個(gè)城市有一個(gè)水晶球的價(jià)格（買入賣出都一樣），他可以經(jīng)過每個(gè)城市多次。問他能掙最多的費(fèi)用為多少？如下圖，假設(shè)城市1~5的價(jià)格為4，3，5，6，1則選擇1-4-5-4-5路線， 掙得5第七頁，共四十七頁，編輯于2023年，星期二分析這是一道非常典型的圖論題,如果有扎實(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)連通分量中進(jìn)行賣出操作,也一定會(huì)選擇賣出價(jià)格最大的那個(gè)點(diǎn).

第八頁，共四十七頁，編輯于2023年，星期二分析所以算法就非常清晰了.首先利用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ā)生棧溢出.參考實(shí)現(xiàn)中采用了非遞歸實(shí)現(xiàn)DFS.第九頁，共四十七頁，編輯于2023年，星期二奇怪的電梯大樓的每一層樓都可以停電梯，而且第i層樓(1<=i<=N)上有一個(gè)數(shù)字Ki(0<=Ki<=N)。電梯只有四個(gè)按鈕：開，關(guān)，上，下。上下的層數(shù)等于當(dāng)前樓層上的那個(gè)數(shù)字。當(dāng)然，如果不能滿足要求，相應(yīng)的按鈕就會(huì)失靈。例如：33125代表了Ki(K1=3,K2=3,……)，從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因?yàn)闆]有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？輸入： 二行，第一行為三個(gè)用空格隔開的正整數(shù)，表示N,A,B(1≤N≤200,1≤A,B≤N)，第二行為N個(gè)用空格隔開的正整數(shù)，表示Ki。輸出：僅一行，即最少按鍵次數(shù),若無法到達(dá)，則輸出-1。第十頁，共四十七頁，編輯于2023年，星期二構(gòu)圖LIFT.IN51533125LIFT.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就行了。

第十一頁，共四十七頁，編輯于2023年，星期二人穿柱子游戲在一個(gè)無限長(zhǎng)的條形路上，有n(n<=200)個(gè)柱子，體積不計(jì)，有一個(gè)人想從左邊走到右邊，人近似看成一個(gè)半徑為R的圓（如下圖），問能否實(shí)現(xiàn)？第十二頁，共四十七頁，編輯于2023年，星期二構(gòu)圖每個(gè)圓的大小完全相同，不存在包含，相切（如果內(nèi)切，就是重合了，如果外切，就是中間不連通的）等等復(fù)雜的關(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)之間是否有路就可以了第十三頁，共四十七頁，編輯于2023年，星期二奇怪的數(shù)列編程輸入3個(gè)整數(shù)n，p，q，尋找一個(gè)由整數(shù)組成的數(shù)列（a1，a2，……，an），要求：其中任意連續(xù)p項(xiàng)之和為正數(shù)，任意連續(xù)q項(xiàng)之和為負(fù)數(shù)。0<n<100，0<p，q<n，若不存在這樣的整數(shù)數(shù)列，則輸出NO；否則輸出滿足條件的一個(gè)數(shù)列即可。輸入格式： 僅一行分別表示n，p，q，之間用一個(gè)空格隔開。

輸出格式： 只有一行，有解即輸出這個(gè)數(shù)列，每個(gè)數(shù)之間用一個(gè)空格隔開。否則輸出NO。第十四頁，共四十七頁，編輯于2023年，星期二分析如果我們按常規(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(0≤i≤n)。顯然根據(jù)題意，有：si<si+p(0≤i≤n-p)si+q<si(0≤i≤n-q)下面，我們把每個(gè)si抽象成一個(gè)點(diǎn)，則根據(jù)上述兩個(gè)不等式可以建立一個(gè)有向圖，圖中共有n+1個(gè)頂點(diǎn)，分別為s0，s1，……，sn。若si>sj(0≤i，j≤n)，則從si往sj引出一條有向邊。第十五頁，共四十七頁，編輯于2023年，星期二構(gòu)圖對(duì)于n=6，p=5，q=3的情況，我們可以建立下圖：第十六頁，共四十七頁，編輯于2023年，星期二對(duì)圖進(jìn)行拓?fù)渑判?；if圖有回路then無解退出else生成拓?fù)湫蛄衞rder[0]…order[n]；那么如果得到了一個(gè)拓?fù)湫蛄?，該如何轉(zhuǎn)換成s數(shù)組呢？因?yàn)橥負(fù)湫蛄兄许旤c(diǎn)對(duì)應(yīng)的s值是遞減的，其中s0=0。如果order[i]=0，則依次設(shè)定sorder[0]=i，sorder[1]=i-1，……，sorder[i-1]=1，sorder[i]=0，sorder[i+1]=-1，……，sorder[n]=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，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ù)。第十七頁，共四十七頁，編輯于2023年，星期二牧場(chǎng)規(guī)劃小可可的好朋友Sealock最喜歡吃花生了，于是借用了小可可的牧場(chǎng)從事花生選種試驗(yàn)。他以網(wǎng)格的方式，非常規(guī)整地把牧場(chǎng)分割成M*N個(gè)矩形區(qū)域(M*N≤5000)，由于各個(gè)區(qū)域中地水面、沼澤面積各不相同，因此各區(qū)域地實(shí)際可種植面積也各不相同，已知區(qū)域(i,j)地可種面積使A(i,j)。每個(gè)區(qū)域種最多只能種植一個(gè)品種地花生?？煞N植面積為零地區(qū)域不能被選擇用來從事選種試驗(yàn)，同時(shí)為了防止花粉傳播到相鄰區(qū)域造成試驗(yàn)結(jié)果不正確，任何兩個(gè)相鄰的區(qū)域都不可以同時(shí)種植花生。這里說的相鄰指的是兩個(gè)區(qū)域有公共邊，僅僅有公共點(diǎn)的兩個(gè)區(qū)域不算做相鄰。小可可準(zhǔn)備幫助Sealock規(guī)劃一下如何選擇種植區(qū)域，才能使得實(shí)際可種植面積總和最大。第十八頁，共四十七頁，編輯于2023年，星期二構(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)方案。ST圖1建立網(wǎng)絡(luò)第十九頁，共四十七頁，編輯于2023年，星期二和平委員會(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<=a<b<=2n，表示這兩個(gè)人是有矛盾的。輸出：無解則輸出NIE。否則打印n行，從小到大輸出你的方案中各人的編號(hào)。任意可行解都是可以的。第二十頁，共四十七頁，編輯于2023年，星期二分析：原題可描述為：有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'）第二十一頁，共四十七頁，編輯于2023年，星期二初步構(gòu)圖如果Ai與Aj不相容，那么如果選擇了Ai，必須選擇Aj‘；同樣，如果選擇了Aj，就必須選擇Ai’。AiAj'AjAi‘這樣的兩條邊對(duì)稱我們從一個(gè)例子來看：第二十二頁，共四十七頁，編輯于2023年，星期二假設(shè)4個(gè)組，不和的代表為：1和4，2和3，7和3，那么構(gòu)圖：13245678假設(shè)：首先選13必須選，2不可選8必須選，4、7不可選5、6可以任選一個(gè)第二十三頁，共四十七頁，編輯于2023年，星期二矛盾的情況為：存在Ai，使得Ai既必須被選又不可選。得到算法1：枚舉每一對(duì)尚未確定的Ai,Ai‘，任選1個(gè)，推導(dǎo)出相關(guān)的組，若不矛盾，則可選擇；否則選另1個(gè)，同樣推導(dǎo)。若矛盾，問題必定無解。13245678第二十四頁，共四十七頁，編輯于2023年，星期二此算法正確性簡(jiǎn)要說明：由于Ai,Ai'都是尚未確定的，它們不與之前的組相關(guān)聯(lián)，前面的選擇不會(huì)影響Ai,Ai'。算法的時(shí)間復(fù)雜度在最壞的情況下為O(nm)。在這個(gè)算法中，并沒有很好的利用圖中邊的對(duì)稱性第二十五頁，共四十七頁，編輯于2023年，星期二先看這樣一個(gè)結(jié)構(gòu)：更一般的說：在每個(gè)一個(gè)環(huán)里，任意一個(gè)點(diǎn)的選擇代表將要選擇此環(huán)里的每一個(gè)點(diǎn)。不妨把環(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同樣如此。圖的收縮13245678第二十六頁，共四十七頁，編輯于2023年，星期二對(duì)于原圖中的每條邊AiAj（設(shè)Ai屬于環(huán)Si，Aj屬于環(huán)Sj）如果Si≠Sj，則在新圖中連邊：SiSj

這樣構(gòu)造出一個(gè)新的有向無環(huán)圖。此圖與原圖等價(jià)。13245678S1

S1'S2

S2'

S3'

S3圖的收縮第二十七頁，共四十七頁，編輯于2023年，星期二算法2通過求強(qiáng)連通分量，可以把圖轉(zhuǎn)換成新的有向無環(huán)圖，在這個(gè)基礎(chǔ)上，介紹一個(gè)新的算法。新算法中，如果存在一對(duì)Ai,Ai‘屬于同一個(gè)環(huán)，則判無解，否則將采用拓?fù)渑判?，以自底向上的順序進(jìn)行推導(dǎo)，一定能找到可行解。第二十八頁，共四十七頁，編輯于2023年，星期二算法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．輸出第二十九頁，共四十七頁，編輯于2023年，星期二瘦陀陀和胖陀陀一場(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è)城市。第三十頁，共四十七頁，編輯于2023年，星期二一個(gè)例子（續(xù)）瘦陀陀正專注地看回家的地圖地圖上標(biāo)有n（n≤200）個(gè)城市和某些城市間直達(dá)的道路以及每條道路的過路費(fèi)瘦陀陀還知道在每一座城市舉辦宴會(huì)的花費(fèi)。給出地圖和A、B的位置請(qǐng)你告訴瘦陀陀回家的最小費(fèi)用你的程序會(huì)接收到多次詢問即對(duì)于每對(duì)城市(c1,c2)，你的程序應(yīng)該立刻給出瘦陀陀從c1到c2的最小花費(fèi)。第三十一頁，共四十七頁，編輯于2023年，星期二分析胖陀陀規(guī)定必須在最貴的城市舉辦宴會(huì)因此不能簡(jiǎn)單地選擇一條最短路走若路上有一個(gè)花費(fèi)特別貴的城市…對(duì)于每個(gè)點(diǎn)X，如果在那里辦宴會(huì)…如何求最短路？多個(gè)詢問怎么處理？floyd計(jì)算每?jī)牲c(diǎn)的距離？SSSP就可以勝任嗎？AB=AX+XB…第三十二頁，共四十七頁，編輯于2023年，星期二樹網(wǎng)的核給出一棵無根樹，邊上有權(quán)。稱樹的最長(zhǎng)路徑為直徑，定義路徑的偏心距為：點(diǎn)到路徑的上的點(diǎn)的最小值的最大值，給出一個(gè)s，找出直徑上的某段長(zhǎng)度不超過s的路徑，使得偏心距最小。

第三十三頁，共四十七頁，編輯于2023年，星期二分析考慮到樹的性質(zhì)，對(duì)于任意兩點(diǎn)，最短路=聯(lián)通路=最長(zhǎng)路。

首先用floyd算法求出任意兩點(diǎn)之間最短路。同時(shí)可以求出最長(zhǎng)路徑上都有哪些點(diǎn)。由于這是一棵樹，最短路必然唯一。設(shè)mid[a,b]是a,b之間的聯(lián)通路上的一個(gè)中間點(diǎn)?？紤]問題的解，構(gòu)造一個(gè)函數(shù)F(k,a,b)為K到ab間的最短路的長(zhǎng)度。則f(k,a,b)=min{d[k,mid[a,b],f[k,a,mid[a,b]],f[k,mid[a,b],b]}

寫出了這個(gè)方程，便不難得出一個(gè)三次方的算法。在實(shí)際做的時(shí)候，可以把k放在最外層枚舉，這樣內(nèi)層實(shí)際上只用到了f的后面2維，用2維數(shù)組記錄即可。

第三十四頁，共四十七頁，編輯于2023年，星期二雙棧排序有兩個(gè)隊(duì)列和兩個(gè)棧,分別命名為隊(duì)列1(q),隊(duì)列2(q2),棧1(s1)和棧2(s2).最初的時(shí)候,q2,s1和s2都為空,而q中有n個(gè)數(shù)(n<=1000),為1~n的某個(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è)操作序列.第三十五頁，共四十七頁，編輯于2023年，星期二考慮單棧例1：1,2,3,4,5例2：5,4,3,2,1例3：3,2,4,5,1例4：3,1,4,5,2no;yes;yes;yes;第三十六頁，共四十七頁，編輯于2023年，星期二定理定理：對(duì)于任意兩個(gè)數(shù)q[i]和q[j]來說,它們不能壓入同一個(gè)棧中的充要條件p是:存在一個(gè)k,使得i<j<k且q[k]<q[i]<q[j].充分性：即如果滿足條件p,那么這兩個(gè)數(shù)一定不能壓入同一個(gè)棧.這個(gè)結(jié)論很顯然,使用反證法可證.

假設(shè)這兩個(gè)數(shù)壓入了同一個(gè)棧,那么在壓入q[k]的時(shí)候棧內(nèi)情況如下:

…q[i]…q[j]…

因?yàn)閝[k]比q[i]和q[j]都小,所以很顯然,當(dāng)q[k]沒有被彈出的時(shí)候,另外兩個(gè)數(shù)也都不能被彈出

而之后,無論其它的數(shù)字在什么時(shí)候被彈出,q[j]總是會(huì)在q[i]之前彈出.而q[j]>q[i],這顯然是不正確的.第三十七頁，共四十七頁，編輯于2023年，星期二證明必要性：也就是,如果兩個(gè)數(shù)不可以壓入同一個(gè)棧,那么它們一定滿足條件p.這里我們來證明它的逆否命題,也就是"如果不滿足條件p,那么這兩個(gè)數(shù)一定可以壓入同一個(gè)棧.“不滿足條件p有兩種情況:一種是對(duì)于任意i<j<k且q[i]<q[j],q[k]>q[i];另一種是對(duì)于任意i<j,q[i]>q[j].第一種情況下,很顯然,在q[k]被壓入棧的時(shí)候,q[i]已經(jīng)被彈出棧.那么,q[k]不會(huì)對(duì)q[j]產(chǎn)生任何影響(這里可能有點(diǎn)亂,因?yàn)榭雌饋?當(dāng)q[j]<q[K]的時(shí)候,是會(huì)有影響的,但實(shí)際上,這還需要另一個(gè)數(shù)R,滿足J<K<R且q[r]<q[j]<q[k],也就是證明充分性的時(shí)候所說的情況…而事實(shí)上我們現(xiàn)在并不考慮這個(gè)r,所以說q[k]對(duì)q[j]沒有影響).第二種情況下,我們可以發(fā)現(xiàn)這其實(shí)就是一個(gè)降序序列,所以所有數(shù)字都可以壓入同一個(gè)棧.

這樣,原命題的逆否命題得證,所以原命題得證.此時(shí),條件p為q[i]和q[j]不能壓入同一個(gè)棧的充要條件也得證.第三十八頁，共四十七頁，編輯于2023年，星期二構(gòu)圖這樣,我們對(duì)所有的數(shù)對(duì)(i,j)滿足1<=i<j<=n,檢查是否存在i<j<k滿足q[k]<q[i]<q[j].如果存在,那么在點(diǎn)i和點(diǎn)j之間連一條無向邊,表示q[i]和q[j]不能壓入同一個(gè)棧.二分圖的兩部分看作兩個(gè)棧,因?yàn)槎謭D的同一部分內(nèi)不會(huì)出現(xiàn)任何連邊,也就相當(dāng)于不能壓入同一個(gè)棧的所有結(jié)點(diǎn)都分到了兩個(gè)棧中.此時(shí)我們只考慮檢查是否有解,所以只要O(n)檢查出這個(gè)圖是不是二分圖,就可以得知是否有解.第三十九頁，共四十七頁，編輯于2023年，星期二深度優(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)都被染色為止.這樣,我們就得到了每個(gè)結(jié)點(diǎn)應(yīng)該壓入哪個(gè)棧中。還有一點(diǎn)小問題,就是如果對(duì)于數(shù)對(duì)(i,j),都去枚舉檢查是否存在k，使得q[k]<q[I]<>M第四十頁，共四十七頁，編輯于2023年，星期二最優(yōu)乘車（NOI97）一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒有一路巴士可以直接到達(dá)S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺(tái)的另一路巴士,這樣換乘幾次后到達(dá)S公園?，F(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ù)第四十一頁，共四十七頁，編輯于2023年，星期二模型的構(gòu)建我們來分析樣例3767473621356747362135第四十二頁，共四十七頁，編輯于2023年，星期二考察4——>7——>3——>6這條線路。由于巴士在同一線路上行走不需換車，我們可設(shè)4——>7，4——>3，4——>6，7—