【正文】 max( 211 ssfn ? 最終復(fù)雜度分析，時間復(fù)雜度大約 O(R3n)（ R 是一行狀態(tài)的組合數(shù)） (3)用貪心解決增加的規(guī)模，從而解決問題 【例四】求網(wǎng)絡(luò)的最小費用最大流。求網(wǎng)絡(luò)的最大流，簡單地說來，是每次尋找一條連接源點和匯點的可增廣路徑并由之擴充網(wǎng)絡(luò)流，直到不存在這樣可增廣路徑，則得出最大流。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—— 用改進算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達 2022 集訓(xùn)隊論文 6 網(wǎng)絡(luò)的費用一般是指在每一段弧上弧的費用與弧的流量的乘積的和。不難看出，可行流每增加 1，所增加的費用都應(yīng)該是最小的（事實上應(yīng)該是減小得最多的）。這樣用貪心的策略就能解決問題了。幸運地，教練可以從 N 個非常棒的選手中選擇隊員，這些選手被標上 1 到 N(3 ≤ N ≤ 500000)。每個選手都參加了每次競賽并且每次競賽都沒有并列的。如果沒有人比 A better，我們就說 A 是excellent。 如數(shù)據(jù)： 96214510783109876543214961710835210 則 excellent 選手是 1， 2， 3， 5。 〖原始算法〗第一眼看到這道題往往想到枚舉。這可以通過另一重循環(huán)，枚舉另一選手 Y，判斷 Y 是否比 X better。因此這一算法的時間復(fù)雜度是 O(N2)，對于這道題，不能滿足要求。不難看出，如果讓 X 依照第一次競賽的名次循環(huán)，枚舉 Y 時只需要枚舉在第一次競賽中排在 X 前面選手即可，因為第一次競賽排在 X 后的選手一定不可能比 X better。 主要流程 2： for(X 從第一次競賽的第 1 名到第一次競賽的第 N 名 ) for(Y 從第一次競賽的第 1 名到第一次競賽的第 (X1)名 ) 判斷 Y 是否比 X better 〖改進二〗如果我們進一步觀察，我們能優(yōu)化上述算法的時間復(fù)雜度。因為如果 Y 比 X better， 從 1 到 2，從 2 到 3—— 用改進算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達 2022 集訓(xùn)隊論文 7 那么 Z 一定比 X better。在判斷 X 是否excellent 的時候，我們只需要在當前的 excellent 選手集合中取得 Y 即可。由于這題 K 可能很大，算法效果仍然不是很理想。 【降維思路】本道題規(guī)模還是很明顯的從二維擴充到三維。 兩次競賽的問題同樣可以套用改進二的普遍算法。參考“主要流程 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 時，我們需要比較 B[A1]與 B[A4]， B[A2]與 B[A4]， B[A3]與 B[A4]，假設(shè) A4 也 是 excellent；??。時間復(fù)雜度竟然達到 O(N)。 【擴展思路】我們怎樣把“改進三”應(yīng)用到三維的情況從而解決問題呢？ 改進三的思路能否再明確些？改進三的本質(zhì)是什么？其實， X 依照第一次競賽的名次循環(huán)， X=Ai 時，因為 )])([m in ( ijABb est ji ?? 中， ji 這樣就保證了Aj在第一次競賽中名次一定比 Ai前；如果 bestiB[Ai]，這樣就保證了 Aj在第二次競賽中名次比 X 前；總之則必然有 Aj比 Ai better。我們假設(shè)這樣一個過程： (1)當 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—— 用改進算法的思想解決規(guī)模維數(shù)增大的問題 廣東省韶關(guān)一中 張偉達 2022 集訓(xùn)隊論文 8 (3)在符合 (1)(2)條件的所有 Aj中找 出 min(C[Aj])，比較 min(C[Aj])與 C[Ai]，若 min(C[Aj])C[Ai]，則保證 Aj 在第三次競賽中名次比 Ai 前，則必有 Aj 比 Ai better， Ai必不是 excellent；反之 Ai是 excellent。 〖改進五〗顯然，如果我們?nèi)匀挥妹杜e的方法來實現(xiàn)第 (2)步，則最終的算法復(fù)雜度仍然是 O(N2)。但是改進四則體現(xiàn)了第二第三次競賽分步選取的思路，利用這一點能否在實現(xiàn)中改進算法的復(fù)雜度呢？ 我們可以比較，改進二和改進四是不同的，在進行了第 (1)步以后，改進二需要同時考慮第二第三次競賽成績，兩次成績同時考慮并不是嚴格有序的，有時候我們不能比較二元組 (B[Ai],C[Ai])與 (B[Aj],C[Aj])的大?。ɡ绠?B[Ai]B[Aj]，但 C[Ai]C[Aj]時）。 〖改進六〗由改進五可以知道，我們單單從改進第 (2)步，時間復(fù)雜度仍然不理想的，能否切實把第 (2)步和第 (3)步結(jié)合起來？經(jīng)過了改進五的改進，我們把查找到的符合 B[Aj]B[Ai](ji)的 Aj 在一個有序數(shù)列中記錄下來，這樣，符合條件的 Aj必然在數(shù)列中是連續(xù)的，設(shè)它是從 D1 到 DK。這樣，第 (3)步又可以簡化為在一段數(shù)列 Ek 中查找最小值，即找 ))(min( KkEk ? 能否在最短時間內(nèi)查找出這個最小值呢？我們需要一種優(yōu)化的數(shù)據(jù)結(jié)構(gòu)來記錄 Dk和 Ek。 插入：加入一對數(shù) (key,value)到數(shù)據(jù)結(jié)構(gòu)中。 因為我們需要的操作與檢索樹擅長的操作很類 似，所以對數(shù)據(jù)結(jié)構(gòu)有一定理解的選手，在這里都能夠想到我們可以構(gòu)造一個二叉檢索樹。例如 1 和 2 的父親是區(qū)間 [1,2]；[1,2]和 [3,4]的父親是 [1,4]，如此類推。 插入和查詢具體做法如下： 插入操作：當我們接到一個請求：把 (a,b)加入到 檢索樹中。 查詢操作：我們要讓檢索樹能夠查詢 key 小于 a 的最小 value。例如當 a=14 時，需要訪問到區(qū)間 [1,8]， [9,12]， [13,13]。到根節(jié)點的時候即可以返回 minvalue。對于每個 X，只要查詢區(qū)間 [1,key]的最小值 minvalue，若 minvaluevalue，則有選手比 X better，即 X 不是 excellent。 由于枚舉 X 循環(huán)需要 O(N)時間，查詢和插入都只需要 O(LogN)，總的時間復(fù)雜度是 O(NLogN)。 【小結(jié)】在這個部分，我們分析了 Team 一題，過程中總結(jié)了很多算法，有的是基本算法，有的是改進不完全的算法。 這一題改進三得出來以后，并沒有而且不能直接得出改進四，而需要很重要的一步 ：分析改進三的本質(zhì)，從而擴展改進三。 四、總結(jié) 這篇論文給大家解釋了筆者關(guān)于規(guī)模維數(shù)增加的一類問題的看法。但本文旨在闡述在解決這類問題的過程中，應(yīng)該結(jié)合算法的本質(zhì)和問題的特點。人類漫長的歷史不就是 開闊進取的精神在支配著，沒有開闊進取，又何來我們今天的發(fā)達的生產(chǎn)力？在 OI 中很多問題我們不能夠