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

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

給出每兩條線是否交叉的信息，請計算辦公室內從左到右各條線的編號第三頁，共四十七頁，編輯于2023年，星期二選址問題現準備在n個居民點v1,v2,…,vn中設置一銀行.問設在哪個點,可使最大服務距離最小?若設置兩個銀行,問設在哪兩個點?模型假設假設各個居民點都有條件設置銀行,并有路相連,且路長已知.第四頁，共四十七頁，編輯于2023年，星期二模型建立與求解用Floyd算法求出任意兩個居民點vi,vj之間的最短距離,并用dij表示.⑴設置一個銀行,銀行設在vi點的最大服務距離為求k,使

即若設置一個銀行,則銀行設在

vk點,可使最大服務距離最小.⑵設置兩個銀行,假設銀行設在vs,vt點使最大服務距離最小.記則s,t滿足：進一步,若設置多個銀行呢？第五頁，共四十七頁，編輯于2023年，星期二求k,使

即若設置一個銀行,則銀行設在

vk點,可使最大服務距離最小.⑵設置兩個銀行,假設銀行設在vs,vt點使最大服務距離最小.記則s,t滿足：進一步,若設置多個銀行呢？第六頁，共四十七頁，編輯于2023年，星期二最優貿易某國有M個城市N條道路，任意兩個城市有道路，有一部分道路為單行線，一部分為雙向道路。某人去該國旅游，從城市1出發到城市n結束，他想做水晶球的生意一次掙點旅行費用，每個城市有一個水晶球的價格（買入賣出都一樣），他可以經過每個城市多次。問他能掙最多的費用為多少？如下圖，假設城市1~5的價格為4，3，5，6，1則選擇1-4-5-4-5路線， 掙得5第七頁，共四十七頁，編輯于2023年，星期二分析這是一道非常典型的圖論題,如果有扎實的圖論基礎解決起來并不困難.解決這道題的關鍵是發現,我們可以將原圖中的任意一個強連通分量收縮為一個點,這個新點的買入價格等于該強連通分量中最小的買入價格,這個新點的賣出價格等于該強連通分量中最大的賣出價格.這是因為,這個新點的性質和一個強連通分量是一樣的,如果我們要在一個強連通分量中進行購買操作,一定會選擇買入價格最小的那個點,如果我們要在一個強連通分量中進行賣出操作,也一定會選擇賣出價格最大的那個點.

第八頁，共四十七頁，編輯于2023年，星期二分析所以算法就非常清晰了.首先利用DFS將所有的強連通分量收縮,這樣我們就可以得到一個有向無環圖G.由于G中沒有環,我們可以對G進行拓撲排序,然后利用遞推求得到達某個點i時,可能的最低買入價格best(i)是多少,以及該點最終能否到達終點.最后對于所有能夠到達終點的點p,設其賣出價格為sell(p),在sell(p)-best(p)中取最大值即得到答案.時間復雜度僅為O(V+E).

在實現的時候最好使用棧消除DFS中的遞歸調用,因為圖中的點可以達到100000,當遞歸深度達到這么大的時候有相當大的幾率發生棧溢出.參考實現中采用了非遞歸實現DFS.第九頁，共四十七頁，編輯于2023年，星期二奇怪的電梯大樓的每一層樓都可以停電梯，而且第i層樓(1<=i<=N)上有一個數字Ki(0<=Ki<=N)。電梯只有四個按鈕：開，關，上，下。上下的層數等于當前樓層上的那個數字。當然，如果不能滿足要求，相應的按鈕就會失靈。例如：33125代表了Ki(K1=3,K2=3,……)，從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？輸入： 二行，第一行為三個用空格隔開的正整數，表示N,A,B(1≤N≤200,1≤A,B≤N)，第二行為N個用空格隔開的正整數，表示Ki。輸出：僅一行，即最少按鍵次數,若無法到達，則輸出-1。第十頁，共四十七頁，編輯于2023年，星期二構圖LIFT.IN51533125LIFT.OUT3對于A樓而言，實際上對它最多只能做2個操作，上到A+X層或下到A-X層，當然前提是存在A+X或A-X層。顯然，如果把每一層樓看做一個頂點，如果A樓可以到B樓，則從頂點A引一條到頂點B的邊，這樣一來，問題就變成了圖論中的兩頂點間最短路徑問題了！當然權設為1就行了。

第十一頁，共四十七頁，編輯于2023年，星期二人穿柱子游戲在一個無限長的條形路上，有n(n<=200)個柱子，體積不計，有一個人想從左邊走到右邊，人近似看成一個半徑為R的圓（如下圖），問能否實現？第十二頁，共四十七頁，編輯于2023年，星期二構圖每個圓的大小完全相同，不存在包含，相切（如果內切，就是重合了，如果外切，就是中間不連通的）等等復雜的關系，只有相交和相離的關系，而且如果2個圓之間相交的話，那么這2個圓就是相通的，可以在這2個圓的圓心之間連一條邊，增加一個源點，與上邊有交點的圓和源點連一條邊，增加一個匯點，與下邊有交點的圓和匯點連一條邊，這樣就把一道幾何題完全轉換成了一道圖論題，只要判斷源點和匯點之間是否有路就可以了第十三頁，共四十七頁，編輯于2023年，星期二奇怪的數列編程輸入3個整數n，p，q，尋找一個由整數組成的數列（a1，a2，……，an），要求：其中任意連續p項之和為正數，任意連續q項之和為負數。0<n<100，0<p，q<n，若不存在這樣的整數數列，則輸出NO；否則輸出滿足條件的一個數列即可。輸入格式： 僅一行分別表示n，p，q，之間用一個空格隔開。

輸出格式： 只有一行，有解即輸出這個數列，每個數之間用一個空格隔開。否則輸出NO。第十四頁，共四十七頁，編輯于2023年，星期二分析如果我們按常規思想，直接將第i個整數ai開始的k個整數之和描述成多項式ai+ai+1+…+ai+k-1的話，問題就很難再往下思考和解決了。所以，我們不防換個角度，暫且撇去每一項數究竟為何值的具體細節，而將注意力集中至連續性這一特點上。設si表示數列前i個整數之和，即si=a1+a2+…+ai。其中s0=0(0≤i≤n)。顯然根據題意，有：si<si+p(0≤i≤n-p)si+q<si(0≤i≤n-q)下面，我們把每個si抽象成一個點，則根據上述兩個不等式可以建立一個有向圖，圖中共有n+1個頂點，分別為s0，s1，……，sn。若si>sj(0≤i，j≤n)，則從si往sj引出一條有向邊。第十五頁，共四十七頁，編輯于2023年，星期二構圖對于n=6，p=5，q=3的情況，我們可以建立下圖：第十六頁，共四十七頁，編輯于2023年，星期二對圖進行拓撲排序；if圖有回路then無解退出else生成拓撲序列order[0]…order[n]；那么如果得到了一個拓撲序列，該如何轉換成s數組呢？因為拓撲序列中頂點對應的s值是遞減的，其中s0=0。如果order[i]=0，則依次設定sorder[0]=i，sorder[1]=i-1，……，sorder[i-1]=1，sorder[i]=0，sorder[i+1]=-1，……，sorder[n]=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，a2=s2-s1=5，a3=s3-s2=-3，a4=s4-s3=-3，a5=s5-s4=5，a6=s6-s5=-3。顯然這個整數數列的任意連續５個整數之和為正，任意連續３個整數之和為負。第十七頁，共四十七頁，編輯于2023年，星期二牧場規劃小可可的好朋友Sealock最喜歡吃花生了，于是借用了小可可的牧場從事花生選種試驗。他以網格的方式，非常規整地把牧場分割成M*N個矩形區域(M*N≤5000)，由于各個區域中地水面、沼澤面積各不相同，因此各區域地實際可種植面積也各不相同，已知區域(i,j)地可種面積使A(i,j)。每個區域種最多只能種植一個品種地花生。可種植面積為零地區域不能被選擇用來從事選種試驗，同時為了防止花粉傳播到相鄰區域造成試驗結果不正確，任何兩個相鄰的區域都不可以同時種植花生。這里說的相鄰指的是兩個區域有公共邊，僅僅有公共點的兩個區域不算做相鄰。小可可準備幫助Sealock規劃一下如何選擇種植區域，才能使得實際可種植面積總和最大。第十八頁，共四十七頁，編輯于2023年，星期二構圖將試驗田轉化為點、并連接相鄰的試驗田后可以發現，我們得到的是一個二分圖。通過對原圖的黑白染色，可以把其中的一部分稱為白點、另一部分稱為黑點。由二分圖建立網絡：加入源點和匯點，從源點向每個白點引一條邊，容量為白點對應試驗田的面積；從每個黑點向匯點引邊，容量為該黑點的對應面積。最后將相鄰點之間的邊改為網絡中的邊，由白點指向黑點，容量為正無窮。通過求網絡最大流得到它的最小割，即為最優方案。ST圖1建立網絡第十九頁，共四十七頁，編輯于2023年，星期二和平委員會（SPO）要選一個委員會，但是出現了一個問題，某些代表是有矛盾的，不能同時選到委員會里來。現在有n個政黨，每個政黨只有兩個代表，要從每個政黨中選擇一個代表，使委員會里的人都是友好的。所有的人用1到2n來編號，2i-1和2i屬于同一個政黨。讀入政黨總數，以及不友好的人的對數。計算是否可以建立委員會。如果可以，給出方案。

輸入：第一行有兩個整數n和m，1<=n<=8000，0<=m<=20000。分別表示政黨的總數以及不友好的關系數。接下來的m行，每行整數a和b,1<=a<b<=2n，表示這兩個人是有矛盾的。輸出：無解則輸出NIE。否則打印n行，從小到大輸出你的方案中各人的編號。任意可行解都是可以的。第二十頁，共四十七頁，編輯于2023年，星期二分析：原題可描述為：有n個組，第i個組里有兩個節點Ai,Ai'。需要從每個組中選出一個。而某些點不可以同時選出（稱之為不相容）。任務是保證選出的n個點都能兩兩相容。（在這里把Ai,Ai'的定義稍稍放寬一些，它們同時表示屬于同一個組的兩個節點。也就是說，如果我們描述Ai，那么描述這個組的另一個節點就可以用Ai'）第二十一頁，共四十七頁，編輯于2023年，星期二初步構圖如果Ai與Aj不相容，那么如果選擇了Ai，必須選擇Aj‘；同樣，如果選擇了Aj，就必須選擇Ai’。AiAj'AjAi‘這樣的兩條邊對稱我們從一個例子來看：第二十二頁，共四十七頁，編輯于2023年，星期二假設4個組，不和的代表為：1和4，2和3，7和3，那么構圖：13245678假設：首先選13必須選，2不可選8必須選，4、7不可選5、6可以任選一個第二十三頁，共四十七頁，編輯于2023年，星期二矛盾的情況為：存在Ai，使得Ai既必須被選又不可選。得到算法1：枚舉每一對尚未確定的Ai,Ai‘，任選1個，推導出相關的組，若不矛盾，則可選擇；否則選另1個，同樣推導。若矛盾，問題必定無解。13245678第二十四頁，共四十七頁，編輯于2023年，星期二此算法正確性簡要說明：由于Ai,Ai'都是尚未確定的，它們不與之前的組相關聯，前面的選擇不會影響Ai,Ai'。算法的時間復雜度在最壞的情況下為O(nm)。在這個算法中，并沒有很好的利用圖中邊的對稱性第二十五頁，共四十七頁，編輯于2023年，星期二先看這樣一個結構：更一般的說：在每個一個環里，任意一個點的選擇代表將要選擇此環里的每一個點。不妨把環收縮成一個子節點（規定這樣的環是極大強連通子圖）。新節點的選擇表示選擇這個節點所對應的環中的每一個節點。此圖中1和3構成一個環，這樣1和3要么都被選擇，要么都不被選。2和4同樣如此。圖的收縮13245678第二十六頁，共四十七頁，編輯于2023年，星期二對于原圖中的每條邊AiAj（設Ai屬于環Si，Aj屬于環Sj）如果Si≠Sj，則在新圖中連邊：SiSj

這樣構造出一個新的有向無環圖。此圖與原圖等價。13245678S1

S1'S2

S2'

S3'

S3圖的收縮第二十七頁，共四十七頁，編輯于2023年，星期二算法2通過求強連通分量，可以把圖轉換成新的有向無環圖，在這個基礎上，介紹一個新的算法。新算法中，如果存在一對Ai,Ai‘屬于同一個環，則判無解，否則將采用拓撲排序，以自底向上的順序進行推導，一定能找到可行解。第二十八頁，共四十七頁，編輯于2023年，星期二算法2的流程：

1．構圖2．求圖的極大強連通子圖3．把每個子圖收縮成單個節點，根據原圖關系構造一個有向無環圖4．判斷是否有解，無解則輸出（退出）5．對新圖進行拓撲排序6．自底向上進行選擇、刪除7．輸出第二十九頁，共四十七頁，編輯于2023年，星期二瘦陀陀和胖陀陀一場可怕的戰爭后，瘦陀陀和他的好朋友胖陀陀將要凱旋。瘦陀陀處在城市A胖陀陀處在另外一個未知的城市他們打算選一個城市X（這個由瘦陀陀來決定）胖陀陀會趕在瘦陀陀之前到達城市X然后等待瘦陀陀也趕到城市X與他匯合，并舉辦一次慶祝宴會（由瘦陀陀請客）接著一起回到他們的家鄉城市B由于胖陀陀嘴饞，他要求舉辦宴會的城市必須是瘦陀陀回家的路線中舉辦宴會最貴的一個城市。第三十頁，共四十七頁，編輯于2023年，星期二一個例子（續）瘦陀陀正專注地看回家的地圖地圖上標有n（n≤200）個城市和某些城市間直達的道路以及每條道路的過路費瘦陀陀還知道在每一座城市舉辦宴會的花費。給出地圖和A、B的位置請你告訴瘦陀陀回家的最小費用你的程序會接收到多次詢問即對于每對城市(c1,c2)，你的程序應該立刻給出瘦陀陀從c1到c2的最小花費。第三十一頁，共四十七頁，編輯于2023年，星期二分析胖陀陀規定必須在最貴的城市舉辦宴會因此不能簡單地選擇一條最短路走若路上有一個花費特別貴的城市…對于每個點X，如果在那里辦宴會…如何求最短路？多個詢問怎么處理？floyd計算每兩點的距離？SSSP就可以勝任嗎？AB=AX+XB…第三十二頁，共四十七頁，編輯于2023年，星期二樹網的核給出一棵無根樹，邊上有權。稱樹的最長路徑為直徑，定義路徑的偏心距為：點到路徑的上的點的最小值的最大值，給出一個s，找出直徑上的某段長度不超過s的路徑，使得偏心距最小。

第三十三頁，共四十七頁，編輯于2023年，星期二分析考慮到樹的性質，對于任意兩點，最短路=聯通路=最長路。

首先用floyd算法求出任意兩點之間最短路。同時可以求出最長路徑上都有哪些點。由于這是一棵樹，最短路必然唯一。設mid[a,b]是a,b之間的聯通路上的一個中間點。考慮問題的解，構造一個函數F(k,a,b)為K到ab間的最短路的長度。則f(k,a,b)=min{d[k,mid[a,b],f[k,a,mid[a,b]],f[k,mid[a,b],b]}

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

第三十四頁，共四十七頁，編輯于2023年，星期二雙棧排序有兩個隊列和兩個棧,分別命名為隊列1(q),隊列2(q2),棧1(s1)和棧2(s2).最初的時候,q2,s1和s2都為空,而q中有n個數(n<=1000),為1~n的某個排列.

現在支持如下四種操作:a操作,將q的首元素提取出并加入s1的棧頂.b操作,將s1的棧頂元素彈出并加入q2的隊列尾.c操作,將q的首元素提取出并加入s2的棧頂.d操作,將s2的棧頂元素彈出并加入q2的隊列尾.請判斷,是否可以經過一系列操作之后,使得q2中依次存儲著1,2,3,…,n.如果可以,求出字典序最小的一個操作序列.第三十五頁，共四十七頁，編輯于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年，星期二定理定理：對于任意兩個數q[i]和q[j]來說,它們不能壓入同一個棧中的充要條件p是:存在一個k,使得i<j<k且q[k]<q[i]<q[j].充分性：即如果滿足條件p,那么這兩個數一定不能壓入同一個棧.這個結論很顯然,使用反證法可證.

假設這兩個數壓入了同一個棧,那么在壓入q[k]的時候棧內情況如下:

…q[i]…q[j]…

因為q[k]比q[i]和q[j]都小,所以很顯然,當q[k]沒有被彈出的時候,另外兩個數也都不能被彈出

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

這樣,原命題的逆否命題得證,所以原命題得證.此時,條件p為q[i]和q[j]不能壓入同一個棧的充要條件也得證.第三十八頁，共四十七頁，編輯于2023年，星期二構圖這樣,我們對所有的數對(i,j)滿足1<=i<j<=n,檢查是否存在i<j<k滿足q[k]<q[i]<q[j].如果存在,那么在點i和點j之間連一條無向邊,表示q[i]和q[j]不能壓入同一個棧.二分圖的兩部分看作兩個棧,因為二分圖的同一部分內不會出現任何連邊,也就相當于不能壓入同一個棧的所有結點都分到了兩個棧中.此時我們只考慮檢查是否有解,所以只要O(n)檢查出這個圖是不是二分圖,就可以得知是否有解.第三十九頁，共四十七頁，編輯于2023年，星期二深度優先搜索求解檢查有解的問題已經解決.接下來的問題是,如何找到字典序最小的解.

實際上,可以發現,如果把二分圖染成1和2兩種顏色,那么結點染色為1對應當前結點被壓入s1,為2對應被壓入s2.為了字典序盡量小,我們希望讓編號小的結點優先壓入s1.又發現二分圖的不同連通分量之間的染色是互不影響的,所以可以每次選取一個未染色的編號最小的結點,將它染色為1并從它開始DFS染色,直到所有結點都被染色為止.這樣,我們就得到了每個結點應該壓入哪個棧中。還有一點小問題,就是如果對于數對(i,j),都去枚舉檢查是否存在k，使得q[k]<q[I]<>M第四十頁，共四十七頁，編輯于2023年，星期二最優乘車（NOI97）一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士,這樣換乘幾次后到達S公園。現在用整數1，2，……N給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號為1，2，……S，公園巴士站的編號為N。寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到S公園的過程中換車的次數最少。輸入N和M條公交線路信息求最少換車的次數第四十一頁，共四十七頁，編輯于2023年，星期二模型的構建我們來分析樣例3767473621356747362135第四十二頁，共四十七頁，編輯于2023年，星期二考察4——>7——>3——>6這條線路。由于巴士在同一線路上行走不需換車，我們可設4——>7，4——>3，4——>6，7—