算法藝術(shù)答案

1、1.1節(jié)習(xí)題1.1.1對(duì)；不對(duì)1.1.2提示：考慮規(guī)模增長(zhǎng)時(shí)的時(shí)間開銷，可以對(duì)比運(yùn)行時(shí)間，也可以在程序中統(tǒng)計(jì)基本操作數(shù)目1.2節(jié)習(xí)題1.2.1不一定。這要看枚舉量和枚舉時(shí)間1.2.3枚舉即可。需要注意的是要保證每個(gè)問題只有一個(gè)正確答案而不是有個(gè)答案。本題有唯一解cdebeedcba。1.2.5注意行有很多但是列不太多。硬幣翻兩次等于不翻，所以所有行/列最多翻一次。枚舉每列是否翻有2”9=512 種情況，此時(shí)可以用O(n)的時(shí)間計(jì)算每行是否翻(注意：列確定以后每行獨(dú)立)。1.2.6只需要枚舉橫坐標(biāo)相鄰的點(diǎn)1.2.7設(shè)S1的長(zhǎng)度為n。注意用串匹配來做的話時(shí)間復(fù)雜度至少為O(10”n)，不是有效算法

2、。應(yīng)該枚舉S1的“分 段方式”。例如231241，如果分段方式為23|124|1，則124為完整的一段，前面必為123,后面必為125, 經(jīng)檢驗(yàn)這是可行的。因此如果有一個(gè)完整段的情況可以用O(n”2)次枚舉來判定。剩下只需要解決沒有完整 段的情況，即被分成兩段。如2312，如果被分為2|312，則需要枚舉位數(shù)。如果是3位，有方程?2 + 1 = 312，無解；如果是4位，有方程?2 + 1 = 312?，有解3122 + 1 = 3123。基本思想如此，但是需要注 意有進(jìn)位的情況。建議讀者自己寫程序并提交到ural在線題庫(kù)檢查自己的程序是否考慮周全。1.2.12首先可以證明：覆蓋整個(gè)草坪當(dāng)且僅

3、當(dāng)覆蓋草坪的上邊界。這樣每個(gè)圓的作用范圍是一條線段，問題轉(zhuǎn)化 為用最少的線段覆蓋整個(gè)區(qū)間。先預(yù)處理再貪心，具體方法留給讀者思考。1.2.14本題較難，需要先推出n=4時(shí)的兩種可能最優(yōu)策略(用代數(shù)方法容易推導(dǎo)出)，然后用遞歸的思想把n4 的情況轉(zhuǎn)化為n=4的情況加以解決。提示：考慮四人速度為1,3,4,5和1,2,5,6的情況，最優(yōu)時(shí)間分別為 16 和 13。1.2.17本題答案不唯一。例如：解方程組。1.2.23枚舉去掉的數(shù)字位置后，幾乎就可以直接解方程了(需要分類討論和少量附加枚舉)。具體方式留給讀者 思考1.2.24把袋子編號(hào)為0,1,2.n-1，如果沒有1717克的限制，就是第0,1,2

4、.n-1個(gè)袋子依次取豌豆0,1,2.n-1 顆，把稱得的重量和0+1+2+.+(n-1)比較，重了幾克就是第幾個(gè)袋子是魔法豌豆！可是現(xiàn)在有總重量限 制，因此只有當(dāng)0+1+2+.+n-1=1717時(shí)才能一次稱出。記M(1)為能保證一次稱出的最大n值，則解不等 式得n=59。二次稱可以用以下策略：59個(gè)袋子為一組，第0組不取，第1組每個(gè)取1顆，第2組每個(gè)取 2顆.只要總重量10000,因此用我們剛才 的策略就可以在10次內(nèi)稱出了。 1.2.27如果某張紙上只有一個(gè)程序，則可以在其他順序恢復(fù)后再單獨(dú)把它插入；如果某張紙上有至少三個(gè)程序， 則除了頭尾之外的中間程序都只會(huì)出現(xiàn)一次，也可以最后處理，因此只

5、需要保留恰好有兩個(gè)程序的紙張。 剩下的工作就不難了，留給讀者思考。1.3節(jié)習(xí)題1.3.6自上而下的讀取各行，可以用本節(jié)介紹的floodfill方法來作，但是更節(jié)省空間的方法是1.4節(jié)介紹的并 查集。需要注意的是要正確的處理新塊開始、舊塊結(jié)束、不同塊合并、相同塊再次合并(形成“洞”)等 幾種情況。1.3.7下確界可以簡(jiǎn)單的通過求輪廓線的并來實(shí)現(xiàn)。交就沒有這么簡(jiǎn)單了，因?yàn)樵谇筝喞€交以后可能形成非矩 形的區(qū)域，即出現(xiàn)“凹角”。先作一次floodfill后刪除有三側(cè)屬于同一個(gè)區(qū)域的角，直到不存在這樣的 角。1.3.24設(shè)電路對(duì)應(yīng)的函數(shù)是f(i)，其中i是一個(gè)n進(jìn)制數(shù)，n為輸入個(gè)數(shù)。如果f(000.0

6、)=f(111.1)，則所有x 設(shè)置為 0 即可。否則考慮序列：000.000,000.001,000.011,000.111, . 011.1, 111.1，每相鄰 兩項(xiàng)只相差一個(gè)字符。顯然一定存在相鄰兩項(xiàng)的f值不同，不同的字符保留為x，其他設(shè)置為相同值即可。 可以二分查找，總時(shí)間復(fù)雜度為O(mlogn)，m為門的數(shù)目。1.4節(jié)習(xí)題1.4.1先作標(biāo)記，等到浪費(fèi)空間大于一半時(shí)重構(gòu)樹?？梢宰C明均攤時(shí)間復(fù)雜度不變。另外還有保持每個(gè)操作最壞 情況時(shí)間復(fù)雜度不變的算法，非常巧妙。1.4.7設(shè) s0=0，si=a1+a2+.+ai，則信息 i j even 等價(jià)于 ai+.+aj為偶數(shù)，即 sj-si-

7、1 為偶數(shù)，即sj與si-1同奇偶。這樣，每條信息都可以變?yōu)槟硟蓚€(gè)si和sj是否同奇偶的信息。記 samei為當(dāng)前和si同奇偶的sj集合，diffi為當(dāng)前和si不同奇偶的sj集合，則一條信息i j even 將導(dǎo)致 samej和 samei-1合并，diffj和 diffi-1合并；信息 i j odd將導(dǎo)致 samej和 diffi-1 合并；diffj和samei-1合并。具體細(xì)節(jié)留給讀者思考。1.4.12和標(biāo)準(zhǔn)的Young Tableau查找算法很類似，稍微修改一下即可。1.4.16先按照x坐標(biāo)排序，然后建立一棵靜態(tài)的BST用于統(tǒng)計(jì)。需要記錄附加信息。建議讀者寫寫程序，要寫得 盡量簡(jiǎn)單，

8、很少幾行即可寫完。1.5節(jié)習(xí)題1.5.8先作減法，把兩個(gè)權(quán)變成一個(gè)?？梢赃M(jìn)一步發(fā)現(xiàn)如果矩形有重疊，可以把重疊部分去掉和權(quán)和保持不變。 這樣問題變成了即找出k個(gè)不重疊的矩形使得權(quán)和最大。們用區(qū)域(i,j)來表示在矩陣W中的“第一行第i 個(gè)格子右邊所有元素加上第二行第j個(gè)格子右邊的所有元素”這個(gè)區(qū)域，用ds,i,j來表示在這個(gè)區(qū)域中 選擇s個(gè)子矩陣，它們的元素總和的最小值。看作多階段決策問題，則決策有五種：決策一：第一行第i 個(gè)格子不用的情況，這種決策轉(zhuǎn)移到狀態(tài)ds,i+1,j；決策二：第二行第j個(gè)格子不用的情況，這種決策 轉(zhuǎn)移到狀態(tài)ds,i,j+1；決策三：第一行從第i個(gè)格子放一個(gè)矩形，則大小L

9、有O(n)種選擇；轉(zhuǎn)移到 ds,i+L,j決策四：第二行從第j個(gè)格子放一個(gè)矩形，則大小L有O(n)種選擇；轉(zhuǎn)移到ds,i,j+L決策五： 兩行一起放寬度為2的矩形，也有O(n)種選擇。1.5.10如果是求利益最大的方案，顯然可以定義狀態(tài)di為考慮前i個(gè)訂單并接受訂單i的最大利潤(rùn)。但是第k 的方案呢？這種狀態(tài)表示是不行的。它的一個(gè)重要問題在于：?jiǎn)栴}不具備最優(yōu)子結(jié)構(gòu)！第k大方案所對(duì)應(yīng) 的決策的子決策不一定是第k大的。無奈之下，我們只好增加一維狀態(tài)參量，用di,j表示考慮前i個(gè)訂 單并介紹訂單i的第j大利潤(rùn)，而狀態(tài)轉(zhuǎn)移時(shí)也必須考慮所有前趨狀態(tài)各自的第1,2,3j大利潤(rùn)(想一想， 為什么不考慮第j+1

10、,j+2k大利潤(rùn)？)，然后加以比較。需要注意的是可以利用堆來降低時(shí)間復(fù)雜度，請(qǐng) 讀者思考。1.5.11注意到命令序列長(zhǎng)度不超過50，機(jī)器人不可能走得太遠(yuǎn)。所以可以先枚舉終止位置，然后單獨(dú)考慮每個(gè)機(jī) 器人，讓每個(gè)機(jī)器人刪除的指令數(shù)都最少。用dx,y,i表示要讓前i條指令被執(zhí)行(或被刪除)后機(jī)器人 處于位置(x,y)所需要?jiǎng)h除的最少指令數(shù)，請(qǐng)讀者列出狀態(tài)轉(zhuǎn)移方程。1.5.12首先，我們直觀的猜測(cè)：任意一副筷子中A和B一定是長(zhǎng)度相鄰的兩只筷子。證明如下：對(duì)于某副筷子 (A1,B1,C1)和另一副筷子(A2,B2,C2)，如果A1=A2=B1=B2，那么交換一下筷子重新組合成(A1,A2,C1)和 (

11、B1,B2,C2)質(zhì)量和會(huì)更優(yōu)。對(duì)于某副筷子(A,B,C)和閑置的筷子D，如果A=D=3j的時(shí)候狀態(tài)是 合法的。請(qǐng)讀者自己寫出狀態(tài)轉(zhuǎn)移方程。1.5.13這道題目有一個(gè)很討厭的條件：“只要有任務(wù)是可以完成的，那么工人不能閑著沒事做”。如果工人必須 按照任務(wù)序號(hào)遞增的順序，那么本題可以用簡(jiǎn)單的動(dòng)態(tài)規(guī)劃解決，但是本題沒有規(guī)定任務(wù)完成的順序，如 果我們用di代表i時(shí)刻以后還需要的最少時(shí)間，那么我們做狀態(tài)轉(zhuǎn)移的時(shí)候會(huì)很為難：我們似乎無法知 道那么任務(wù)是已經(jīng)完成了的(它們不能被重復(fù)執(zhí)行)，因此決策集合無法確定。即：?jiǎn)栴}有后效性！ 真是這樣嗎？(解決后效性的通常辦法是增加狀態(tài)參量，即記錄已經(jīng)有哪些任務(wù)完成了

12、，但是這樣做狀態(tài) 量會(huì)大增，并不是一個(gè)好辦法)我們需要避免重復(fù)選擇任務(wù)，但是細(xì)心的讀者一定已經(jīng)發(fā)現(xiàn)了：根本不會(huì) 重復(fù)選擇任務(wù)。原因在于一個(gè)容易被忽略的條件：t=di-ai2ti。當(dāng)完成一個(gè)任務(wù)以后，嚴(yán)格的時(shí)間期限 已經(jīng)不可能允許工作再重復(fù)選擇這個(gè)任務(wù)了。接下來的任務(wù)就十分簡(jiǎn)單了，請(qǐng)讀者自己思考。1.5.17提示：本題很容易想到O(n”3)的直接動(dòng)態(tài)規(guī)劃，但是時(shí)間復(fù)雜度還可以降低。先連接各點(diǎn)和圓心，把面積 最大轉(zhuǎn)化為正弦函數(shù)和最大，再利用正弦函數(shù)的性質(zhì)進(jìn)行優(yōu)化。1.5.18鐵球下落的高度和總是一定的，所以我們關(guān)心的問題只是它的水平移動(dòng)距離。我們稱平臺(tái)i的兩頭為平臺(tái) 端點(diǎn)的橫坐標(biāo)為xi,0和xi,

13、1,并設(shè)端點(diǎn)i縱坐標(biāo)為yi。為方便處理，我們將鐵球的初始位置抽象 成寬度為0的平臺(tái)0。每落到一個(gè)平臺(tái)，球有兩種決策：向左滾和向右滾，因此我們?cè)O(shè)從平臺(tái)i的第k個(gè)邊緣（k=0為左邊緣，k=1 為右邊緣）落下后還需要移動(dòng)的最少水平距離為di,k。設(shè)pi,k為從平臺(tái)i的第k個(gè)邊緣落下后到達(dá)的 平臺(tái)編號(hào)（即狀態(tài)di,k 描述的“當(dāng)前平臺(tái)”，如果落下會(huì)摔碎，則pi,k=-1），則兩種決策是： 決策一：向左滾，指標(biāo)函數(shù)為 dpi,k,0 + |xi,k - xpi,k,0| 決策二：向右滾，指標(biāo)函數(shù)為 dpi,k,1 + |xi,k - xpi,k,1|狀態(tài)數(shù)為O（n），決策數(shù)為0（1），動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜

14、度取決于狀態(tài)轉(zhuǎn)移的時(shí)間復(fù)雜度，即p數(shù)組的計(jì)算復(fù) 雜度。我們可以從高到低依次考察平臺(tái)i下面平臺(tái)j，如果xi,k處于區(qū)間xj,0, xj,1內(nèi)，貝 pi,k=j。最壞情況下的時(shí)間復(fù)雜度為0（n”2），比動(dòng)態(tài)規(guī)劃本身還要高。事實(shí)上可以用BST或者線段樹來 做到O（nlogn），請(qǐng)讀者思考。1.5.19本題最大的迷惑點(diǎn)在于佳佳的籃子，如果你在記錄當(dāng)前糖果堆的同時(shí)記錄籃子內(nèi)的糖果，那么你就上當(dāng)了。 佳佳很聰明，他只記錄當(dāng)前糖果堆的情況，從而推知哪些糖果曾被拿到籃子里，并標(biāo)記編號(hào)為i的糖果總 共被拿出來Ai顆。本著將盡可能多的糖果放入口袋的原則，佳佳將能配對(duì)的糖果統(tǒng)統(tǒng)從籃子內(nèi)取出，于是令A(yù)i =Ai mo

15、d 2, 則當(dāng)前籃子里糖果的數(shù)量Tot=sumAi就求出了。我們用P1,P2,P3,P4分別表示當(dāng)前4堆糖果剩余的糖果數(shù)量，用數(shù)組元素aP1,P2,P3,P4表示狀態(tài) P1,P2,P3,P4相應(yīng)的Tot值。顯然，根據(jù)aP1,P2,P3,P4+1的值，我們可以推得aP1,P2,P3,P4的值。如 果TotW5，那么狀態(tài)P1,P2,P3,P4是合法的，記為dP1,P2,P3,P4 = true；否則，這是導(dǎo)致游戲結(jié)束的 非法狀態(tài)，記為dP1,P2,P3,P4 = false。根據(jù)這個(gè)布爾型狀態(tài)定義，我們不難寫出狀態(tài)轉(zhuǎn)移方程，請(qǐng)讀 者自己完成。1.5.21本題也是利用匹配點(diǎn)的稀疏性。1.5.22只需

16、求原串和逆序串的LCS1.5.23標(biāo)準(zhǔn)的LIS問題1.6節(jié)習(xí)題1.6.1按照拓?fù)漤樞騺硭阉鳎聪人炎罾飳幼犹炱?，再次里?可以用后文提到的極端法剪枝（估計(jì)天平兩邊的 最大、最小可能取值）1.6.7仔細(xì)分析一下狀態(tài)空間，你會(huì)發(fā)現(xiàn)它其實(shí)非常少，用簡(jiǎn)單的啟發(fā)函數(shù)（例如只考慮檔住的縱向車移動(dòng)的最 小步數(shù)和與Car0步數(shù)之和）就可以取得非常好的效果。1.6.8此題比較難?？梢岳肐DA*搜索，忽略湖泊后用網(wǎng)絡(luò)流的方法求出的割點(diǎn)數(shù)目（事實(shí)上還不完全是割點(diǎn)， 因?yàn)橛行c(diǎn)被屏蔽掉了）作為h函數(shù)，加上可行性剪枝：如果可以加石頭的地方都加了石頭還是能相互看 見，則剪枝。h函數(shù)和可行性剪枝的作用都非常明顯，讀者不妨

17、一試。1.6.16對(duì)于大多數(shù)數(shù)據(jù)來說，預(yù)處理合并掉相同的塊并事先保存好每個(gè)塊右方和下方可能的塊集合后速度將會(huì)非 ?？臁?.1節(jié)習(xí)題2.1.2先考慮n=2”k的情況，構(gòu)造完成后任意n都能處理了。2.1.3先展開 mk - (m-1)k = A(m) = akT*m”(kT) + ak-2*m”(k-2) + .，其中 A(m)為 m 的 k-1 次多項(xiàng) 式。代入 m=1,2,3.n 后左右相加得到 nk = ak-1*s(k-1,n) + ak-2*s(k-2,n) + .其中 ak為 A(m)的 k 次項(xiàng)系數(shù)?？捎么朔◤?s(1,n), s(2,n) . s(k-1,n)計(jì)算 s(k,n)。2

18、.1.6解方程組。2.1.9列出方程組以后發(fā)現(xiàn)可以直接遞推計(jì)算而不需高斯消元。2.1.10解方程組。2.1.11解方程組。注意特殊情況的處理。建議讀者自己分析。2.1.14n=50時(shí)不管m為幾一定有解。2.2節(jié)習(xí)題2.2.6提示：2”k步以后的情形很有規(guī)律。利用這個(gè)規(guī)律可以用二分法逐步用2”k逼近n。2.3節(jié)習(xí)題2.3.3類似15數(shù)碼問題的處理方法，參見書p190頁(yè)2.4節(jié)習(xí)題缺少的提示：2.4.1; 2.4.2; 2.4.7; 2.4.92.4.3 Gridland其實(shí)這道題目只需要考慮兩種情況。情況一：兩個(gè)邊長(zhǎng)至少有一個(gè)是偶數(shù)長(zhǎng)度為：2*(height-1)+2*(width-1)+(he

19、ight-2)*(width-2)=2*height-2+2*width-2+height*width-2*height-2*width+4=height*width情況二：兩個(gè)邊長(zhǎng)都是奇數(shù)長(zhǎng)度為：Height*width 1 + sqrt(2) 因?yàn)樯僖粭l直邊但是多一個(gè)斜邊。2.4.4郵遞員首先讓我們把報(bào)酬的問題理清楚。如果期望值為Wi的村子是郵遞員第Ki個(gè)經(jīng)過的不 同村子，那么他會(huì)得到報(bào)酬Wi-Ki元；同時(shí)在郵遞員走過所有M條路后，他會(huì)從郵局那里 得到m元，所以無論郵遞員怎么走，只要他完成了任務(wù)，報(bào)酬都是叩+i + m。這樣i=1i=1報(bào)酬的問題就不用考慮了，需要解決的只剩如何完成任務(wù)。因

20、為每個(gè)村子只可能處于兩條路的十子路口上，或者四條路的米子路口上，或者一條路的中 央，所以與每個(gè)村子相連的路的條數(shù)為偶數(shù)。這個(gè)村落的構(gòu)造符合一筆畫的充要條件，剩下 的問題唯有求歐拉回路。2.4.5城市觀光首先，完成所有旅程后的興趣值為一定的。如果這個(gè)興趣值小于0則必然不能滿足要求， 也就是說總的興趣值大于0是路徑存在的必要條件。那么是否有滿足題意的充分條件呢？實(shí) 際上，總的興趣值大于0就是路徑存在的充分必要條件，構(gòu)造如下：由于每個(gè)點(diǎn)的度都為4,所以圖中必然存在歐拉回路，找出一條這樣的歐拉回路。從任意一點(diǎn)出發(fā)，找到權(quán)最小的一個(gè)位置。如果這個(gè)位置的權(quán)是正的，則這條路經(jīng)已經(jīng) 滿足要求。因?yàn)檫@個(gè)權(quán)是最小

21、的負(fù)權(quán)，設(shè)為-a(a0)。所以從這個(gè)點(diǎn)出發(fā)，回到起點(diǎn)的權(quán)至少為a。 而由于是最小負(fù)權(quán)，所以在從起點(diǎn)到這個(gè)點(diǎn)的這段路徑中所有點(diǎn)的權(quán)都大于-a。換句話 說，如果將這個(gè)權(quán)最小的點(diǎn)作為新起點(diǎn)，則從原起點(diǎn)到這個(gè)點(diǎn)的路徑上的所有點(diǎn)的權(quán)均 大于0。同時(shí)，由于這個(gè)點(diǎn)的權(quán)最小，所以在從這個(gè)點(diǎn)到起點(diǎn)的路徑中所有的點(diǎn)的權(quán)也 都大于0。滿足題目要求。所以，只要構(gòu)造出一條回路，就總能在這條回路上找到一個(gè)點(diǎn)作為起點(diǎn)，滿足題目要求。2.4.6賭博機(jī)我們來分析一下機(jī)器失敗的苛刻條件。首先抽象模型：賭博機(jī)是圖(稱為圖T1)中的 頂點(diǎn)，如果賭博機(jī)x的集合中有一個(gè)數(shù)y，那么向圖中添加一條從x指向y的有向邊。僅當(dāng) 此圖構(gòu)成一個(gè)頂點(diǎn)1

22、出度比入度大一，頂點(diǎn)n入度比出度大一，其余頂點(diǎn)入度等于出度的歐 拉路時(shí)，機(jī)器才有可能失敗。所以下面我們只針對(duì)此種情況進(jìn)行討論：如果機(jī)器沒有失敗，那么圖中剩余邊構(gòu)成殘留圖t3,機(jī)器運(yùn)作路徑構(gòu)成圖t2, t2是一 個(gè)頂點(diǎn)1出度比入度大一，頂點(diǎn)n入度比出度大一，其余頂點(diǎn)入度等于出度的歐拉路。因?yàn)?T1-T2=T3，所以T3是頂點(diǎn)n入度出度皆為0其余所有頂點(diǎn)入度等于出度的歐拉回路。既然 是回路就必然包含圈，事實(shí)上，只要?dú)埩魣Dt3是個(gè)圈而非沒有邊的空?qǐng)D，機(jī)器就不會(huì)失敗。 我們從每個(gè)頂點(diǎn)出發(fā)，找尋不包含頂點(diǎn)n的圈。如果找不到，那么機(jī)器失?。蝗绻业搅?， 那么把這個(gè)圈從圖T1中刪除，剩下的圖便是使得機(jī)器獲勝

23、的路徑，而這個(gè)路徑仍然是個(gè)頂 點(diǎn)1出度比入度大一，頂點(diǎn)n入度比出度大一，其余頂點(diǎn)入度等于出度的歐拉路。2.4.8遠(yuǎn)程通信例子給出的方案是怎樣找到的呢？我們可以這樣來分析:對(duì)于Bornholm端口 2Gotland 端口 1、Gotland端口 4,由于沒有其它端口以它們?yōu)槟康亩丝?，所以它們必須被設(shè)置成發(fā) 送模式，因此一一對(duì)應(yīng)的Gotland端口 5、Bornholm端口 4、Bornholm端口 1必須為接收模 式。刪除由Gotland端口 5、Bornholm端口 4、Bornholm端口 1發(fā)出的有向邊。結(jié)果發(fā)現(xiàn)， 由于邊的刪除,Gotland端口 3、Bornholm端口 3也成為只有發(fā)

24、送模式?jīng)]有接受模式的端口， 所以它們必須被設(shè)置成發(fā)送模式，相應(yīng)的Gotland端口 2為接受模式。參照樣例的解題方法，對(duì)于任意待匹配的通訊圖，我們不斷找出只有發(fā)送(接受)模式 的端口 x,確定它們以及相應(yīng)接受(發(fā)送)端口 y的運(yùn)行方式，將點(diǎn)x、y及相關(guān)邊從圖中 刪除。如此迭代，直至無點(diǎn)、邊可刪?？紤]當(dāng)前剩余通訊圖，圖中共有a+b個(gè)點(diǎn)，a+b條有 向邊，每個(gè)點(diǎn)入度出度皆為1。這樣的圖只能由若干個(gè)有向環(huán)構(gòu)成。倘若某個(gè)有向環(huán)頂點(diǎn)個(gè) 數(shù)為奇數(shù)，那么此通訊圖無合法匹配方案；否則對(duì)于每個(gè)環(huán)任意確定某個(gè)端口為發(fā)送模式， 其余端口的運(yùn)行模式也就相應(yīng)確定了。2.4.10龍穴迷宮圖中部分點(diǎn)是重復(fù)的，于是想到不斷把

25、重復(fù)的點(diǎn)合并，以求出最少的點(diǎn)數(shù)。按的定義進(jìn)一步定義Fk：描述以點(diǎn)k為起點(diǎn)到點(diǎn)n的路徑，其中IWkWn,有：(1, colork ) + F (P,C)F (P, C) = (2, colork) + F (P, C), F = (, colorn)心由-1(3, colork) + F , (P, C)nIek ,3顯然，若F = F ，且e豐e ，則可以將點(diǎn)e與點(diǎn)e合并，這樣既減少了頂 ek ,iek, jk ,ik, jk ,ik, j點(diǎn)數(shù)目又不會(huì)影響Fk，更不會(huì)改變F,。進(jìn)而推廣到更一般的情況，只要F=F.，即可合并點(diǎn) i與點(diǎn)j。由于Fn至F由簡(jiǎn)變繁，不難想到，從Fn起一步一步向上推導(dǎo)，

26、逐步合并點(diǎn)。有向無環(huán)圖層次分明，定義deepi:表示點(diǎn)；到點(diǎn)n的最大步數(shù)，顯然有：deepn = 0deepi = maxdeepe ,deepe ,deepe (1 i n 1)i ,1i ,2i ,3若deepideepj，則F.與烏.中序列的最大長(zhǎng)度不等，一定有F.P,?？梢姡c(diǎn)i和 點(diǎn)j若可以和并，i、j 一定在同一層中。于是從deep=0的點(diǎn)n起，逐層合并點(diǎn)。當(dāng)deepi=deepj，因?yàn)樵搶右韵碌狞c(diǎn)已合 并過，只需符合條件colori=colorj匕廣 j （1 r 3）（i、j三邊指向的點(diǎn)相同）， 即 可判斷出F=F.，合并點(diǎn)i和點(diǎn)j。算出合并后圖的點(diǎn)數(shù)，即為所求。需要注意的是，

27、合并點(diǎn)時(shí)，需改變相關(guān)的e值。2.4.11追捕游戲我們把棋盤上的每一個(gè)格子作為一個(gè)點(diǎn)，如果兩個(gè)格子相鄰，就在相應(yīng)的兩個(gè)點(diǎn)之間 連上一條邊。由題意知，圖中不存在一個(gè)由3個(gè)點(diǎn)組成的環(huán)。根據(jù)題意，如果B抓不到A， 那么這個(gè)游戲就可以一直進(jìn)行下去。所以，我們的首要任務(wù)是判斷什么情況下B抓不到A。憑直覺我們可以想到：如果A能夠成功到達(dá)一個(gè)環(huán)上的某一點(diǎn)，那么A就不會(huì)被B抓 住了（因?yàn)锳可以順著這個(gè)環(huán)和B兜圈子）。但是，這樣的解釋是不充分的。下面我們就給 出一個(gè)嚴(yán)格的證明。證：我們先作一個(gè)定義：一個(gè)點(diǎn)如果出現(xiàn)在某個(gè)環(huán)上，那么我們就把它稱為安全點(diǎn)。根據(jù)環(huán)的含義，每個(gè)安全點(diǎn)至少和兩個(gè)安全點(diǎn)相連否則它就不可能出現(xiàn)在

28、一個(gè)環(huán)上。 由于題目中規(guī)定，圖中不存在一個(gè)由3個(gè)點(diǎn)組成的環(huán)，所以與一個(gè)點(diǎn)相鄰的所有點(diǎn)相互之 間不相鄰。所以，如果玩家A位于一個(gè)安全點(diǎn)P，玩家B走到了與？相鄰的點(diǎn)Q上，則必 定存在一個(gè)與安全點(diǎn)P相鄰的安全點(diǎn)R，滿足R與Q不相同。而且，R與Q 一定不相鄰。 如果B所在的點(diǎn)與A不相鄰，那么A就可以留在原地不動(dòng)。所以，A總是可以位于一個(gè)與 B不相鄰的安全點(diǎn)上，這樣B就永遠(yuǎn)抓不到A。在A沒有能到達(dá)安全點(diǎn)之前，它所能到的點(diǎn)都不是安全點(diǎn)，所以不存在過這些點(diǎn)的環(huán)。 這些點(diǎn)必定構(gòu)成一棵樹。如果以A的出發(fā)點(diǎn)作為根R，那么要從根R的一棵子樹上的某一 點(diǎn)到達(dá)另一棵子樹上的某一點(diǎn)，必須要經(jīng)過根R （在完整的圖中也是如此

29、）。否則我們就可 以得到一個(gè)過根R的環(huán)，與根R不是安全點(diǎn)矛盾。同理，對(duì)于根R的一個(gè)兒子Q，Q的一 棵子樹上的某一點(diǎn)到達(dá)另一棵子樹上的某一點(diǎn)，必須要經(jīng)過 Q （在完整的圖中也是如 此）。因此，B 一定會(huì)在樹中的X點(diǎn)上第一次出現(xiàn)，這個(gè)X是一定的。（當(dāng)B的出發(fā)點(diǎn) 在樹上時(shí)，這個(gè)X就是他的出發(fā)點(diǎn)）。在A沒有到達(dá)安全點(diǎn)之前，他到樹上的每一個(gè)點(diǎn)都只有一條路。他應(yīng)當(dāng)事先定好一個(gè) 目標(biāo)，朝著一個(gè)希望點(diǎn)走（我們把與安全點(diǎn)相鄰的樹上的點(diǎn)稱為希望點(diǎn)）。如果要改變目標(biāo)， 他就只能走回頭路，這樣顯然是不合算的。所以A無法根據(jù)B的走法來及時(shí)調(diào)整自己的策 略。而B的目標(biāo)也是相當(dāng)明確的，就是朝著根的方向走，盡快地卡住要道。因

30、為，隨著樹 的深度的增加，分叉會(huì)越來越多，其中有希望點(diǎn)的幾率也相應(yīng)增大。對(duì)于樹上的某一個(gè)點(diǎn)P，如果X是P的一棵子樹上的點(diǎn)、在P的另一棵子樹上有希望 點(diǎn)，那么若A能夠比B早一輪到達(dá)P，A就一定能安全到達(dá)安全點(diǎn)。反之，如果對(duì)于所有 這樣的P，A都不能比B早到，那么A的所有通向安全點(diǎn)的道路都會(huì)被B堵死，A遲早會(huì) 被B抓到。這里R和X都在樹上，所以R和X到樹上的點(diǎn)的路線都是唯一的。所以，我們可以 用寬度優(yōu)先搜索來判斷究竟是A能率先到達(dá)安全點(diǎn)還是B能搶先一步卡住咽喉要道。我們首先要找出所有的安全點(diǎn)。我們從點(diǎn)1開始做寬度優(yōu)先搜索。每出現(xiàn)一條橫向邊， 就表示找到了一個(gè)環(huán)。找出這個(gè)環(huán)上的所有點(diǎn)，然后把它們都記

31、為安全點(diǎn)。接著，我們用寬度優(yōu)先搜索分別計(jì)算每一回合后A、B兩人可以到達(dá)的格子。我們先 搜B的，再搜A的（這和題中兩人走棋的順序相反）。對(duì)于一個(gè)點(diǎn)，如果B已經(jīng)到達(dá)過了， 那么A就不能再去了，否則就一定會(huì)被抓住。如果A能安全到達(dá)一個(gè)安全點(diǎn)，那么B就再 也抓不到A 了，程序就應(yīng)該馬上終止。當(dāng)B能到達(dá)所有A能到達(dá)的格子后，那么A就無路 可走了。這時(shí)所用的步數(shù)就是B抓到A所需要的步數(shù)。我們要開一個(gè)布爾型數(shù)組，記錄每個(gè)點(diǎn)是否為安全點(diǎn)。在寬度優(yōu)先搜索中還需要開幾 個(gè)數(shù)組。在解題的過程中，我們只用到了寬度優(yōu)先搜索，所以算法的時(shí)間復(fù)雜度是O(n+m)，其 中n是格子的個(gè)數(shù)，m是相鄰的格子的對(duì)數(shù)。由于m15000

32、且n3000，所以這個(gè)算法是非 常理想的。程序的空間需求也不大，大約為300k。2.5節(jié)習(xí)題2.5.1最公平路從小到大枚舉最小邊，則最大邊不減。每次用O(m)的時(shí)間判連通即可。2.5.3最小圈初始時(shí)設(shè)置di,i=無窮大，再套用floyd-warshall算法即可。2.5.6路的最小公倍數(shù)單獨(dú)考慮每個(gè)素?cái)?shù)a，那么一條路p的s(p)值中a的指數(shù)就是p上的權(quán)中a的最小指數(shù)， 即路的“瓶頸”。所有s(p)的最小公倍數(shù)就是所有路的瓶頸最大值。把“求和”操作改成“取 最小值”操作，然后套用dijkstra即可。2.5.7貨幣兌換這道題目的本質(zhì)是判斷加權(quán)有向圖是否有正圈，套用bellman-ford算法即可

33、。如果迭代 n-1次以后標(biāo)號(hào)仍然會(huì)改變，則有正圈。為了找到正圈，需要記錄每個(gè)標(biāo)號(hào)變化最后一次是 由那個(gè)結(jié)點(diǎn)引起的。2.5.8速度限制如果每條道路都有限速標(biāo)志，那么此問題只是最普通的最短路徑?；诖耍覀儑L試給 每條道路標(biāo)上限速標(biāo)志。無標(biāo)志路徑的速度由上一條道路的速度決定；如果上一條道路亦無標(biāo)志，那么它們的速 度又由上兩條道路的速度決定；如果上兩條道路亦無標(biāo)志，那么它們的速度又由上三條道路 的速度決定如此向前追溯，直至遇到有標(biāo)志路徑或者起點(diǎn)。所以逆向思維，我們從每一 條有標(biāo)志路徑或者起點(diǎn)出發(fā)，在它們的后面接上所有單獨(dú)的或者一串連續(xù)的無標(biāo)志路徑，使 之成為一條有限速標(biāo)志的新路。這樣，此問題就轉(zhuǎn)化為

34、普通最短路徑。當(dāng)然，如何求出所有 單獨(dú)的或者一串連續(xù)的無標(biāo)志路徑可以用O(n3)的Floyd算法。2.5.9會(huì)議呼叫首先，激活的邊是不可能產(chǎn)生環(huán)的，所以形成了一棵樹，而且只有一個(gè)分叉點(diǎn)。先從A， B，C出發(fā)調(diào)用SSSP，這一步是O(m+nlogn)的。然后枚舉這個(gè)分叉點(diǎn)x，讓dA,x+dB,x+dC,x 盡量大。這一步是O(n)的。2.5.11開發(fā)計(jì)劃這道題目是“航天計(jì)劃問題”的直接推廣。2.5.12因特網(wǎng)寬帶這是個(gè)普通的最大流的模型。不同于一般書上此類算法之處在于，本題是無向圖的關(guān)系， 所以每條?。▋牲c(diǎn)之間的路徑）是無向的，因此在具體計(jì)算過程中，每次找最短路進(jìn)行增流， 弧的實(shí)際方向是動(dòng)態(tài)變化

35、的，這就需要進(jìn)行判斷。判斷的方法也很簡(jiǎn)單：設(shè)從知個(gè)點(diǎn)對(duì)第 J個(gè)點(diǎn)進(jìn)行分析的，記流量為F，容量為C，那么如果Fi,jj；如果Fj,i 0，那么可以進(jìn)行反向擴(kuò)展。2.5.13出題者的煩惱X結(jié)點(diǎn)是題目，Y結(jié)點(diǎn)是類別，如果題目a屬于類別b則連邊Xa-Yb，容量為1。對(duì)于 每個(gè)Xa，連邊s-Xa，容量為1。對(duì)于每個(gè)Yb，連邊Yb-t，容量為第b類需要的試題數(shù)目。 注意本題不是求最大流而是固定流量為給定數(shù)k的流，因此用增廣路算法比較合適，每次流 量增加1（因此ford-fulkerson算法是不適用的?。『脼閗時(shí)停止。2.5.14馬戲團(tuán)本題是標(biāo)準(zhǔn)的最小路徑覆蓋問題。2.5.15錦標(biāo)賽X結(jié)點(diǎn)是還沒有進(jìn)行的比賽，Y結(jié)點(diǎn)是人，如果比賽a的雙方是p和q，則連邊Xa-Yp 和Xa-Yq，容量都為1。對(duì)于每個(gè)比賽a，連邊s-Xa，容量為1；對(duì)于每個(gè)人a，連邊Ya-t， 容量為直觀的說，這個(gè)容量是此人能取勝的最大場(chǎng)數(shù)。枚舉冠軍，則最好情況就是讓他所 有比賽都取得勝利，然后枚舉第二名取勝的