【正文】 連一條容量無窮大、權(quán)值為0的邊，代表座位在這一段可以是空閑的?？偟膩碚f，模型中的一個單位流就代表了一個座位。 為了避免最大費(fèi)用流這個怪異的名詞，在實(shí)現(xiàn)時把權(quán)值改為1即可。最小費(fèi)用流的算法中，用BellmanFord算法求一次最短路需要O(K*N)，最大流量等于座位數(shù)C，所以算法的總復(fù)雜度是O(K*N*C)，無法承受題目給出的數(shù)據(jù)規(guī)模。加入貪心思想 給這個特殊的圖套上最小費(fèi)用流算法的確有點(diǎn)浪費(fèi)，時間復(fù)雜度高是必然的結(jié)果。那么如何利用這些特殊點(diǎn)優(yōu)化算法呢？ 費(fèi)用流算法中，每次找到一條最短路徑（權(quán)和最小的路徑）進(jìn)行擴(kuò)展。擴(kuò)展時為了可能的改動，我們會給擴(kuò)展邊的反向邊擴(kuò)大容量，這個處理解決了后效性的問題。仔細(xì)想想，在這個問題中或許根本就不存在后效性，我們能不能放棄對反向邊的處理？ 不處理反向邊使算法有了本質(zhì)上的改變。它所做的相當(dāng)于：逐一安排每一個座位，使每個座位在當(dāng)前情況下全程載牛數(shù)最大。對此，我們不必再用BF算法，動態(tài)規(guī)劃可以在O(K)時間內(nèi)得出答案。這樣，總時間復(fù)雜度降到了O(K*C)，足以滿足題目所給的數(shù)據(jù)規(guī)模。 但是這個算法存在反例：圖2 反例的圖示起點(diǎn)終點(diǎn)路線A路線B路線C路線D 如圖2，假設(shè)這4條路線中都只有1頭牛，那么一架配有兩個空位的飛機(jī)就可以為所有的4頭牛服務(wù)。但是以上的貪心算法很有可能會為第一個座位安排A、D中的兩頭牛，因?yàn)椴淮嬖谝粋€3頭牛的安排方案。這樣一來，第二個座位無論如何都只能將一頭牛帶到目的地了。算法的確只能保證結(jié)果是很不錯的，不一定最優(yōu)。 即使這樣，這仍然是一個正確率較高的算法。在實(shí)際測試中，它通過了官方16組測試數(shù)據(jù)中的15組。深入判斷邊與邊的關(guān)系 繼續(xù)分析上一個算法。對于一個座位的方案而言，如果存在兩條邊，無論方案選擇哪一條最終能座上這個座位的總牛數(shù)都一樣，算法就會認(rèn)為兩條邊是一樣好的，但這時它們之間可能仍有優(yōu)劣之分。所以接下來我們需要更深入地判斷邊與邊之間的優(yōu)劣關(guān)系。 邊之間的優(yōu)劣關(guān)系判斷起來并不簡單，因?yàn)槊織l邊都有兩個參數(shù)——起點(diǎn)和終點(diǎn)。處理這類問題的一個普遍方法是使一個參數(shù)有序化，但這里好像并不適用。不過換一個角度想，假如在某一個機(jī)場，兩頭牛搶一個位子，我們會把這個座位分給誰？當(dāng)然是目的地較近的那個。如此的思維方式使我們很自然地丟掉了起點(diǎn)這個因素：它們無論是從哪兒上來的都不會對這個決定造成影響。 于是，我們得到了一個新的貪心模式： 一站一站地處理。飛到某個飛機(jī)場時，在要上機(jī)的牛與已經(jīng)在飛機(jī)上的牛中選擇目的地最近的C個，讓它們坐上/留在飛機(jī)上一起前往下一站。有些?？赡軙谥型颈或?qū)逐下機(jī)，有些不牛道，但這個算法無疑是正確而且簡潔的。 用數(shù)組記錄飛機(jī)上的牛，每一站進(jìn)行一次O(C)的成員更新，可以得到一個O(N*C)的高效算法。一些實(shí)現(xiàn)上的技巧還可以將其優(yōu)化到O(N)。回顧與啟示 回顧全過程，嘗試動態(tài)規(guī)劃失敗，我們退回到一個低起點(diǎn)：網(wǎng)絡(luò)流算法。在優(yōu)化過程中，首先對網(wǎng)絡(luò)流算法加入貪心思想。發(fā)現(xiàn)反例后，分析問題所在、調(diào)整貪心角度，從而得到了一個正確且更加高效的算法。最后，我們會發(fā)現(xiàn)這仍然是一個類似動態(tài)規(guī)劃的算法（只是在選擇最優(yōu)狀態(tài)時運(yùn)用了貪心思想），雖然一開始就想到動態(tài)規(guī)劃，但是我們對其中的很多細(xì)節(jié)不知所措。于是我們以標(biāo)準(zhǔn)的網(wǎng)絡(luò)流算法為基礎(chǔ)，進(jìn)行大膽地猜想，發(fā)現(xiàn)猜想錯誤后分清問題所在并嘗試改進(jìn)，最終得到了動態(tài)規(guī)劃的具體方法。 思路受阻時，我們需要這樣的猜想。如果猜想正確，算法的設(shè)計(jì)得以繼續(xù)；即使錯誤，往往也不用放棄已有的結(jié)果。一個錯誤的猜想至少會讓問題的一部分更加明朗，加以分析、糾正后，同樣可以得到令人滿意的結(jié)果。 分析錯誤的能力為大膽猜想提供了保障。[例] 漁網(wǎng) 題目來源：ICPC 2001上海賽區(qū)，F(xiàn)ishing Net。 漁網(wǎng)的洞越小，捕到的魚就越多。因此，漁民們在捕魚回來后，都要檢查一下漁網(wǎng)上有沒有大的洞，以便在下次出海之前，將這些洞補(bǔ)好。 漁網(wǎng)被簡單的看作一個由頂點(diǎn)和邊構(gòu)成的圖。如果圖中每一個長度大于3的圈，中間都至少有一段漁網(wǎng)（連接圈上兩個頂點(diǎn)，且不在圈上的邊）將其隔開，這個漁網(wǎng)就是完美的。請判斷輸入的漁網(wǎng)是否完美。初步分析 說到漁網(wǎng)，很容易讓人認(rèn)為所給的圖是一個平面圖。但仔細(xì)看看題目中對漁網(wǎng)的說明就會發(fā)現(xiàn)，由漁網(wǎng)得到的圖其實(shí)是任意的。 這是一道標(biāo)準(zhǔn)的弦圖判定問題（判斷一個圖是不是弦圖）。題目中已經(jīng)對弦圖做了形象的解釋，這里再給出一個更明確的定義：弦 圖 如果在一個圖中，每一個長度大于三的環(huán)都至少有一條弦，那么這個圖是一個弦圖(chordal graph)。弦是連接環(huán)上兩個不相鄰頂點(diǎn)的一條邊。 為了方便說明，有弦的環(huán)將被簡稱為合法環(huán)，有弦的路徑將被簡稱為合法路徑。 弦圖判定已有一個形式優(yōu)美、時間復(fù)雜度為O(M)的算法，這個算法足以用來解決這道題目。但是在信息學(xué)競賽中，有關(guān)弦圖的問題極其罕見，而這個算法以巧妙的數(shù)學(xué)變換為基礎(chǔ)，針對性很強(qiáng)，所以對我們來說價(jià)值并不大。它的具體思路與實(shí)現(xiàn)在[1]中有詳細(xì)描述，本文不再關(guān)注。下面我們將討論的是另一個更加直觀的算法。使用搜索枚舉環(huán) 出于對弦圖的定義最直接的理解，我們應(yīng)該先設(shè)法找到圖中的環(huán)并加以判斷。任意的圖并沒有什么優(yōu)秀的性質(zhì)可言，直接在其中尋找環(huán)將是盲目而低效的（例如枚舉長度然后枚舉這一長度的頂點(diǎn)序列）。我們應(yīng)該先將數(shù)據(jù)的結(jié)構(gòu)簡化。 基本搜索算法就可以做到這一點(diǎn)，它將圖有序化從而得到搜索樹。樹是無環(huán)的，而環(huán)恰恰是我們所找的。這一點(diǎn)提醒我們將目光轉(zhuǎn)向樹枝（前向邊）以外的邊。 在進(jìn)一步的思考之前，讓我們先來解決另外一個問題——深搜還是廣搜？這個選擇直接影響著以后的判斷方法。 不妨先用手工的方法試試：145231452314523圖3 生成樹的對比 原圖 深搜樹 廣搜樹 前面已經(jīng)提到了接下來的焦點(diǎn)將是樹外的邊。由圖3可以看出，這些邊在深搜樹中以后向邊的形式出現(xiàn)，在廣搜樹中以橫叉邊的形式出現(xiàn)（這兩點(diǎn)也可由各自的搜索順序經(jīng)過簡單的推理得到）。這個差別很難讓我們做出一個很肯定的結(jié)論，但至少從表面上看后向邊所連接的祖孫關(guān)系要比橫叉邊連接的兄弟關(guān)系簡單。所以為了討論的進(jìn)一步展開，我們選擇深度優(yōu)先搜索。 至此，我們有了一個算法的輪廓：在圖上進(jìn)行深度優(yōu)先遍歷，在發(fā)現(xiàn)后向邊時檢查與它相關(guān)的環(huán)。通過遞推檢查環(huán) 如果我們把對應(yīng)著合法環(huán)的后向邊稱為合法后向邊的話，那么剩下的問題就是如何判斷后向邊是否合法。很自然的，我們需要知道后向邊的兩端在加入后向邊之前的距離是多少。如果距離大于二，那么就找到了一個不合法的圈。事實(shí)上我們根本不用求出具體的距離，只要知道一個節(jié)點(diǎn)的祖先節(jié)點(diǎn)中，哪些離它一條邊遠(yuǎn)、哪些離它兩條邊遠(yuǎn)。這需要用兩個二維布爾型數(shù)組來記錄（第一個其實(shí)就是鄰接矩陣的一部分）。 算法實(shí)現(xiàn)時，我們可以通過遞推快速地維護(hù)第二個數(shù)組。整理主體算法 梳理一下得到的整個算法： 在圖上進(jìn)行深度優(yōu)先遍歷。每到一個待擴(kuò)展節(jié)點(diǎn)時，首先根據(jù)它的父節(jié)點(diǎn)將它到所有祖先節(jié)點(diǎn)的距離初始化，然后逐一檢查從它連出的所有后向邊，并更新與它祖先節(jié)點(diǎn)之間的距離。距離確定后，再次檢查所有后向邊。如果某一條后向邊所連接的兩點(diǎn)距離大于二，則判定圖不是弦圖，退出搜索。否則開始擴(kuò)展當(dāng)前節(jié)點(diǎn)的后代。 由于檢查后向邊時要更新當(dāng)前節(jié)點(diǎn)到祖先節(jié)點(diǎn)的距離，是O(N)的。而后向邊的個數(shù)是O(M)級別的。所以這個算法的總時間復(fù)雜度為O(M*N)，對于題目中(N≤1000, M=O(N2))來說，這個復(fù)雜度是不可接受的。但考慮到內(nèi)層循環(huán)操作的是布爾型數(shù)組，我們可以進(jìn)行適當(dāng)?shù)目臻g壓縮：將32個布爾型變量存儲到一個32位整型變量中。這不會影響到算法的時間復(fù)雜度，但可以很實(shí)際地將運(yùn)行時間減少到將近十分之一。環(huán)在搜索樹中的多種形態(tài) 上一節(jié)中，我們得到了一個在題目數(shù)據(jù)規(guī)模內(nèi)效率接近O(M)的新算法?？墒巧约哟蜁l(fā)現(xiàn)，算法的構(gòu)建中有幾處并不嚴(yán)密。圖4 主要考慮短環(huán)的一個原因長環(huán)短環(huán) 先說明一個小問題。對于一個較長的環(huán)，如果還有一些點(diǎn)和邊間接地連著環(huán)上不相鄰的點(diǎn)，就會出現(xiàn)長度更小的環(huán)（如圖4）；否則，它本身會被算法找出并判斷為不合法（從下面的分析中可以看出）。所以我們暫時放開長環(huán)，以長度最短的不合法環(huán)C4（長度為4的無弦環(huán)）為例討論改進(jìn)辦法。 C4在深搜樹中出現(xiàn)的三種形態(tài)： 非法環(huán)上的點(diǎn)或邊 其他點(diǎn)或邊圖5 C4出現(xiàn)在深搜樹中的三種可能形態(tài) 目前的算法所能判斷到的環(huán)只有第一種。這是由于在另外兩種情況下，環(huán)上的邊都有一條以上不在搜索樹上。 解決辦法有兩種：一、加入另外的判斷過程；二、設(shè)法將三種情況統(tǒng)一后處理。 經(jīng)過簡單的嘗試發(fā)現(xiàn)，逐一處理另外兩種情況有一定困難，而且這有可能使算法難以實(shí)現(xiàn)。恰好又有一個簡單的方法可以把各種情況統(tǒng)一，它就是隨機(jī)化。 三種情況的出現(xiàn)可以認(rèn)為是等概率的，利用排列組合的知識容易得到下面這樣一個表：隨機(jī)化次數(shù)123456漏掉某個特定C4的概率%%%%%% 不難看出，經(jīng)過幾次反復(fù)求解后，即使圖中只有一個不合法環(huán)，它被遺漏的概率也已經(jīng)十分小了。具體實(shí)現(xiàn)中，選擇在5次以上就完全可以滿足題目的要求了。環(huán)與環(huán)之間的屏蔽長度為2的合法路徑被屏蔽的不合法路徑正在檢查的后向邊 圖 6 反例的圖示 以上的算法成功地通過了ZOJ 浙江大學(xué)在線題庫。上的9組數(shù)據(jù)，它對隨機(jī)圖的判斷幾乎不會出錯。但遺憾的是，反例仍然存在。在之前的討論中，我們忽略了：一條后向邊對應(yīng)的環(huán)可能不止一個。 求距離時，我們得到的是其中最短的一個環(huán)減去后向邊后的長度。即使這個環(huán)合法，也還有可能存在其它更長的環(huán)。所以實(shí)際的效果是，當(dāng)算法判定一條后向邊不合法時，圖中一定有不合法環(huán)；然而當(dāng)算法判定一條后向邊合法時，它仍有可能不合法。我們所判定的只是后向邊合法的必要條