【文章內(nèi)容簡介】 地說來，是每次尋找一條連接源點(diǎn)和匯點(diǎn)的可增廣路徑并由之?dāng)U充網(wǎng)絡(luò)流，直到不存在這樣可增廣路徑，則得出最大流。 那么，又 如何把費(fèi)用也考慮進(jìn)去呢？我們先來看看網(wǎng)絡(luò)的費(fèi)用的定義吧。H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H H P P P P P P P P P P P P P P P P P P P P 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 6 網(wǎng)絡(luò)的費(fèi)用一般是指在每一段弧上弧的費(fèi)用與弧的流量的乘積的和。（弧的費(fèi)用由可能為負(fù)）所以網(wǎng)絡(luò)的最小費(fèi)用最大流是指可行流中費(fèi)用最小的。不難看出，可行流每增加 1，所增加的費(fèi)用都應(yīng)該是最小的（事實(shí)上應(yīng)該是減小得最多的）。這樣可以得出一個(gè)改進(jìn)：每次選取一條費(fèi)用最?。ǘ曳钦┑目稍鰪V路徑，直到最終不存在費(fèi)用非正的可增廣路徑。這樣用貪心的策略就能解決問題了。 (4)多種途徑的綜合運(yùn)用 【例五】 Team Selection (Balkan OI 2022 Day1) 【題目大意】 IOI 要來了， BP 隊(duì)要選擇最好的選手去參加。幸運(yùn)地，教練可以從 N 個(gè)非常棒的選手中選擇隊(duì)員，這些選手被標(biāo)上 1 到 N(3 ≤ N ≤ 500000)。為了選出的選手是最好的，教練組織了三次競賽并給出每次競賽排名。每個(gè)選手都參加了每次競賽并且每次競賽都沒有并列的。當(dāng) A 在所有競賽中名次都比 B 前，我們就說 A 是比 B better。如果沒有人比 A better，我們就說 A 是excellent。求 excellent 選手的個(gè)數(shù)。 如數(shù)據(jù)： 96214510783109876543214961710835210 則 excellent 選手是 1， 2， 3， 5。 【原始思路】一拿到這一題，很容易會(huì)有以下的思路。 〖原始算法〗第一眼看到這道題往往想到枚舉。簡單地根據(jù) better和 excellent的定義，現(xiàn)只需要枚舉每一個(gè)選手 X，判斷 X 是否 excellent。這可以通過另一重循環(huán)，枚舉另一選手 Y，判斷 Y 是否比 X better。判斷是容易的，我們只需要簡單地判斷 X 和 Y 的三次排名。因此這一算法的時(shí)間復(fù)雜度是 O(N2)，對于這道題，不能滿足要求。 主要流程 1： for(X 從 1 到 N) for(Y 從 1 到 N) 判斷 Y 是否比 X better 〖改進(jìn)一〗 原始算法是可以改進(jìn)的。不難看出，如果讓 X 依照第一次競賽的名次循環(huán)，枚舉 Y 時(shí)只需要枚舉在第一次競賽中排在 X 前面選手即可，因?yàn)榈谝淮胃傎惻旁?X 后的選手一定不可能比 X better。不過這樣小的改進(jìn)提起來只是開闊開闊思路，它對時(shí)間復(fù)雜度不會(huì)有太大影響。 主要流程 2： for(X 從第一次競賽的第 1 名到第一次競賽的第 N 名 ) for(Y 從第一次競賽的第 1 名到第一次競賽的第 (X1)名 ) 判斷 Y 是否比 X better 〖改進(jìn)二〗如果我們進(jìn)一步觀察，我們能優(yōu)化上述算法的時(shí)間復(fù)雜度。我們發(fā)現(xiàn)：如果 Y 不是 excellent（因?yàn)橛?Z 比 Y better），當(dāng)我們檢查 X 是否 excellent時(shí)，我們檢查了 Z 是否比 X better 的話，可以不檢查 Y。因?yàn)槿绻?Y 比 X better， 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 7 那么 Z 一定比 X better。然后可以通過簡單地修改“改進(jìn)一”。在判斷 X 是否excellent 的時(shí)候，我們只需要在當(dāng)前的 excellent 選手集合中取得 Y 即可。 主要流程 3： for(X 從第一次競賽的第 1 名到第一次競賽的第 N 名 ) for(Y 枚舉當(dāng)前已知的 excellent) 判斷 Y 是否比 X better 這樣，我們能把時(shí)間復(fù)雜度減少到 O(NK)（設(shè) K 是 excellent 選手的個(gè)數(shù)）。由于這題 K 可能很大，算法效果仍然不是很理想。 【原始思路小結(jié)】這里的原始算法是直接根據(jù)原始模型模擬出來的，改進(jìn)一和改進(jìn)二都單純地根據(jù)原始算法的設(shè)計(jì)缺陷來“改進(jìn)”（這個(gè)改進(jìn)沒有利用問題的特殊性，不是本文所要闡述的“改進(jìn)”），所以最后的時(shí)間復(fù)雜度沒有質(zhì)的進(jìn)展。 【降維思路】本道題規(guī)模還是很明顯的從二維擴(kuò)充到三維。所以還是先用降維的思想，我們先解決選手之間只進(jìn)行兩次競賽的問題。 兩次競賽的問題同樣可以套用改進(jìn)二的普遍算法。為了方便說明，我們設(shè)第一次競賽排名依次為 Ai（表示第一次競賽的第 i 名是 Ai）， Ai 號(hào)選手在第二次競賽中的排名的為 B[Ai]（注意 B[Ai]與 Ai的含義不同）。參考“主要流程 3”：先是 X=A1，顯然 A1 是 excellent；接著 X=A2，只需要比較 B[A1]與 B[A2]大小，不妨假設(shè) B[A2]B[A1]，則 A2 也是 excellent；接下來， X=A3，我們需要比較 B[A1]與 B[A3]， B[A2]與 B[A3]??假設(shè) A3 也是 excellent； X=A4 時(shí)，我們需要比較 B[A1]與 B[A4]， B[A2]與 B[A4]， B[A3]與 B[A4]，假設(shè) A4 也 是 excellent；??。也許這里有心人會(huì)發(fā)現(xiàn)什么，對了，比較 B[A1]與 B[X]， B[A2]與 B[X]， B[A3]與 B[Ai]??的時(shí)候，只要有任何一個(gè) B[Aj]B[Ai](ji)， Ai 就不是 excellent 的，那么，我們只需要用 min(B[Aj])與 B[Ai]比較！ 〖改進(jìn)三〗（適用于兩次競賽）以上我們看到了一個(gè)特殊的例子：兩次排名完全相反，但是我們可以從中提煉出可行的改進(jìn)算法：對于兩次競賽的情況，當(dāng)X=Ai時(shí)，設(shè) )])([m in ( ijABb est ji ?? ，則 B[Ai]只需要與 besti比較 即可。時(shí)間復(fù)雜度竟然達(dá)到 O(N)。 【降維思路小結(jié)】在這次分析中，我們從兩次競賽 —— 簡化后的問題出發(fā)，通過簡單的觀察和思考，得出了改進(jìn)的算法，但是優(yōu)化后的算法要應(yīng)用到三維的情況還有很長的路要走。 【擴(kuò)展思路】我們怎樣把“改進(jìn)三”應(yīng)用到三維的情況從而解決問題呢？ 改進(jìn)三的思路能否再明確些？改進(jìn)三的本質(zhì)是什么？其實(shí)， X 依照第一次競賽的名次循環(huán)， X=Ai 時(shí)，因?yàn)?)])([m in ( ijABb est ji ?? 中， ji 這樣就保證了Aj在第一次競賽中名次一定比 Ai前；如果 bestiB[Ai]，這樣就保證了 Aj在第二次競賽中名次比 X 前；總之則必然有 Aj比 Ai better。 〖改進(jìn)四〗能否把改進(jìn)三擴(kuò)展到三次競賽上面去呢？為了方便說明，我們還需要設(shè)第三次競賽中 Ai選手名次為 C[Ai]。我們假設(shè)這樣一個(gè)過程： (1)當(dāng) X=Ai，設(shè) ji，則可以保證 Aj在第一次競賽中名次比 Ai前，若不存在這樣的 j，則 Ai是 excellent； (2)在符合 (1)條件的所有 Aj中找出能滿足 B[Aj]B[Ai]的選手，保證 Aj在第二次競賽中名次比 Ai前，若不存在這樣的 j，則 Ai是 excellent； 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 8