最新二分圖匹配及其應用課件

二分圖匹配及其應用二分圖匹配及其應用目錄增廣路定理與Hall定理二分圖最大基數(shù)匹配二分圖最大權(quán)匹配應用目錄增廣路定理與Hall定理2最新二分圖匹配及其應用課件3最新二分圖匹配及其應用課件4最新二分圖匹配及其應用課件5最新二分圖匹配及其應用課件6最新二分圖匹配及其應用課件7最新二分圖匹配及其應用課件8Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要增廣次關(guān)鍵：用O(m)時間找一個極大最短增廣路集步驟1：用距離標號擴展匈牙利樹，找到第一個未蓋點時并不停止，把此時的距離標號設為上限。這樣，找到的所有未蓋點距離標號都相同步驟2：每次任取一個未蓋點，用DFS找到它到起點的增廣路(只沿著距離標號下降的方向),標記經(jīng)過的點,找所有增廣路的總時間為O(m)Hopcroft算法可以證明：如果每次找到的最短增廣路集是極9基于DFS的算法從貪心匹配,而不是空匹配開始每次從一個未蓋點開始DFS找增廣路,而不是一次性把所有未蓋點放入隊列進行BFS如果從一個未蓋點u開始找不到增廣路,則以后再也不用考慮u了.為什么?定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配的增廣路基于DFS的算法從貪心匹配,而不是空匹配開始10定理的證明(1)定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配M’的增廣路證明:假設增廣后從u出發(fā)有增廣路Q.若Q與P不相交,則Q就是M-增廣路,矛盾.因此Q與P相交.下面借助P和Q構(gòu)造出從u出發(fā)關(guān)于M的增廣路,從而得到矛盾定理的證明(1)定理:假設G的匹配為M,不存在從非飽和點11定理的證明(2)Q與P相交.設P的兩個M-非飽和點為u0和v0,而Q的兩個M’-非飽和點是u,v.從u開始沿Q走,設第一個P中結(jié)點為w,則w把P分為兩段,其中必有一段以M中邊與w關(guān)聯(lián),得到從u出發(fā)增廣路wv0u0vuPQ定理的證明(2)Q與P相交.設P的兩個M-非飽和點為u0和12完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個非負整數(shù)權(quán)值目標：求出權(quán)和最大的完美匹配特點：完美匹配容易求，但權(quán)最大的不易可行頂標：結(jié)點函數(shù)l，對任意弧(x,y)滿足相等子圖：G的生成子圖，包含所有點，但只包含滿足l(x)+l(y)=w(x,y)的所有弧(x,y)完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個非負整數(shù)權(quán)13相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)匹配證明：設M*是相等子圖的完美匹配，則根據(jù)定義設M是原圖的任意完美匹配，則關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)14算法思想關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配思想：隨便構(gòu)造一個可行頂標（例如Y結(jié)點頂標為0，X結(jié)點的頂標為它出發(fā)所有弧的最大權(quán)值，然后求相等子圖的最大匹配存在完美匹配，算法終止否則修改頂標使得相等子圖的邊變多，有更大機會存在完美匹配考慮相等子圖不存在完美匹配時的情形算法思想關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配15Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為6，不是完美匹配算法在尋找增廣路失敗的同時得到了一棵匈牙利樹雖然此匈牙利樹并沒有包含未蓋點（因此沒有找到增廣路），但仍然含有重要信息Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為16Kuhn-Munkres算法設匈牙利樹中的X結(jié)點集為S，Y結(jié)點集為T，則S到T沒有邊（否則匈牙利樹可以繼續(xù)生長）S到T的邊都是非匹配邊（想一想，為什么）但若把S中所有點的頂標同時減少一個相同整數(shù)a，則S到T中可能會有新邊進入相等子圖SSTTKuhn-Munkres算法設匈牙利樹中的X結(jié)點集為S，Y結(jié)17Kuhn-Munkres算法把S中所有點的頂標同時減少一個相同整數(shù)a，則S到T中可能會有新邊進入相等子圖為了保證S-T的匹配邊不離開相等子圖，把T中所有點的頂標同時增加aSSTT-a+a為保證有新邊進入，取如果S中每個頂標的實際減小值比這個值小則不會有新邊進入；如果比這個值大則頂標將變得不可行Kuhn-Munkres算法把S中所有點的頂標同時減少一個相18Kuhn-Munkres算法設邊(x,y)進入相同子圖y是未蓋點，則找到增廣路y和S中的點z匹配，則把z和y分別加入S和T中每次修改頂標要么找到增廣路，要么使匈牙利樹增加兩個結(jié)點因此一共需要O(n2)次修改頂標操作關(guān)鍵：快速修改頂標SSTT-a+aKuhn-Munkres算法設邊(x,y)進入相同子圖SST19頂標的修改方法1：枚舉S和T中的每個元素，根據(jù)定義計算最小值，每次修改的時間為O(n2)，總O(n4)方法2：對于T中的每個元素y，定義松弛量則a的計算公式變?yōu)轫敇说男薷姆椒?：枚舉S和T中的每個元素，根據(jù)定義計算最小值20頂標的快速修改每次增廣后用O(n2)時間計算所有點的初始slack，由于每次生長匈牙利樹時所有S-T弧的增量相同，因此修改每個slack值只需要常數(shù)時間，計算所有slack值需要O(n)時間每次增廣后最多修改n次頂標，因此每次增廣后修改頂標總時間降為O(n2)，總O(n3)結(jié)論：Kuhn-Munkres算法的總時間復雜度為O(n3)頂標的快速修改每次增廣后用O(n2)時間計算所有點的初始sl21例題1.BelovedSons(SGU210)國王有N個兒子，另外有N漂亮的女孩，每個兒子喜歡其中的某些。國王對每個兒子有一個喜愛程度。要把王子和這些女孩配對（不一定完全配對），使得所有被配對的王子被喜愛程度值的平方和盡可能大。例題1.BelovedSons(SGU210)國王有N22分析可以用二分圖的最佳匹配因為這個圖有特殊性，男孩子一邊任一個點連出的所有邊的權(quán)值都是相同的，所以只要將男孩子按照國王的喜歡程度從大到小排序，先對國王更喜歡的孩子擴展增廣路徑，就可以得到最優(yōu)解。這是為什么呢？分析可以用二分圖的最佳匹配23分析由增廣路的性質(zhì)可以知道一條增廣路的應用只可能在匹配的男孩子中加入一個人，而不可能刪去任意一個人。所以國王喜歡程度較低的男孩子進入匹配不可能對喜歡程度較高的孩子是否在匹配中產(chǎn)生任何影響：這就是貪心算法成立的原因。分析由增廣路的性質(zhì)可以知道一條增廣路的應用只可能在匹配的男孩24例題2.Dominoes(SGU190)給定一個N×N的棋盤，其中有一些格子被移除。要求在剩下的棋盤中放置互不重疊的1×2的骨牌，將棋盤蓋滿。例題2.Dominoes(SGU190)給定一個N×N的棋25分析將棋盤黑白染色，使得黑格周圍都是白格，白格周圍都是黑格。黑白格構(gòu)成了二分圖的兩個頂點集合，相鄰的格子之間有邊。這樣，二分圖的完備匹配就是問題的解了。實際上不需要單獨建立二分圖，直接在圖上操作即可。點和邊都是O(N2)個,因此時間復雜度為O(N3)分析將棋盤黑白染色，使得黑格周圍都是白格，白格周圍都是黑格。26例題3.Speleology(POI9906)一個山上有一個很大的洞，其中有n個室，編號為1~n，室與室之間有通道。編號越大的室在越下方。有一批洞穴學者要從編號為1的室走到編號為n的室中，途中他們只能從編號小的地方走到編號大的地方。每條和1或n相連的通道只允許一個人通過。問：最多可以有多少名洞穴學者？例題3.Speleology(POI9906)一個山上有一27分析我們可以把n個室看作n個點，把通道看作是點到點之間的一條有向邊。那么本題就是一個典型的網(wǎng)絡流問題。其中，每條和1或n相連的邊容量為1,其他邊容量為無窮大。1為源點，n為匯點。這個網(wǎng)絡的最大流即為問題的解其實這個圖是特殊的,考慮1出發(fā)直接可達集合S和直接可達n的集合T之間的最大匹配分析我們可以把n個室看作n個點，把通道看作是點到點之間的一28例題4.UnstableSystems(SGU218)求一個完備匹配，使得匹配邊中權(quán)值最大的邊權(quán)值最小。例題4.UnstableSystems(SGU218)求29分析算法一二分選擇flow，并且進行最大匹配算法二從權(quán)值最低的邊開始，每次增加一條邊。維護交錯樹森林，最多只可能增加一個交錯軌。因為找到N條交錯軌即可，而維護交錯樹森林的平攤復雜度為O(1)，所以總時間復雜度依然為O(N3)分析算法一30例題5.GreedyIsland(ZOJ1638)有n(<=10,000)種卡片，每種卡片上有三種屬性：攻擊、防御、超能力從n張卡片中選A張作為攻擊卡片，B張作為防御卡片，C張作為超能力卡片(A+B+C<=100)。要求攻擊卡片的總攻擊值、防御卡片的總防御值和超能力卡片的總超能力值之和盡量大例題5.GreedyIsland(ZOJ1638)有n31分析令A+B+C=m，則m<=100如果一張卡片被選為攻擊卡片，則它的攻擊值不可能排不到前m位（這樣前m位肯定有沒選的，換成它則提高攻擊值）這樣，只需要保留攻擊、防御和超能力各前100名，一共最多3m張（有重復的話比這個少）。分析令A+B+C=m，則m<=10032分析算法一：構(gòu)造二分圖，左邊3個點，表示攻擊、防御、超能力三個用途；右邊3m個點，表示所有需要考慮的卡片，則時間復雜度為O(m3)。算法二：左邊只有3個點，因此可以設d[i,a,b,c]表示前i張選了a張攻擊卡片，b張防御卡片，c張超能力卡片，則狀態(tài)轉(zhuǎn)移是O(1)的（考慮下一張卡片的四種決策），狀態(tài)不超過m4/9個，仍然高效分析算法一：構(gòu)造二分圖，左邊3個點，表示攻擊、防御、超能力三33例題6.DivideandConquer(SGU229)N*N的方格上有一些格子著黑色.把它們分成兩部分,使得其中一部分逆時針旋轉(zhuǎn)90度、180度或270度后再平移,可以和另一部分重合例題6.DivideandConquer(SGU22934分析枚舉旋轉(zhuǎn)角度和平移向量,枚舉量O(n2)每個點變換后有一個唯一的象.對于每個黑點p,如果它的象也是黑點,則連一條有向邊則問題有解當且僅當此圖有完美匹配如果得到的圖有度數(shù)為0的點或者自環(huán),顯然沒有匹配,否則圖是鏈和環(huán)的集合,各個連通分量很容易求出各自的最大匹配時間復雜度為:O(n4)分析枚舉旋轉(zhuǎn)角度和平移向量,枚舉量O(n2)35例題7.整數(shù)因子團問題給整數(shù)n,考慮集合{1,2,…,n}.每次可以選擇集合中的一個元素k,刪除它和它在集合中的所有因子,要求每次至少刪除兩個數(shù)(即k至少有一個小于k的約數(shù)在集合中)例如,n=6時方案一:依次選5,6,剩余序列為4方案二:依次選5,4,6,剩余序列為空輸入n(<=120),求一種方案讓選擇的數(shù)之和盡量大.注意選擇的數(shù)并不等同于刪除的數(shù)例題7.整數(shù)因子團問題給整數(shù)n,考慮集合{1,2,…36分析似乎并沒有很好的方法,搜索吧下界:一個不錯的解,先貪心,搜索過程中不斷改進為當前得到的最優(yōu)解上界:對當前狀態(tài)的估計,應被設計為狀態(tài)的函數(shù).因為頻繁調(diào)用,計算量不應太大關(guān)鍵:最優(yōu)性剪枝當前分數(shù)+當前狀態(tài)的上界<=下界分析似乎并沒有很好的方法,搜索吧37貪心先考慮只有兩個約數(shù)的數(shù)中最大的一個,如果沒有,再考慮只有三個約數(shù)的數(shù)中最大的一個.只有一種情況例外:如果q有一個倍數(shù)p,使得邊p->q存在且p出發(fā)只有一條邊.刪除q會讓p沒有辦法刪除,還不如主動選擇p,效果是一樣的.如果有多個p,顯然應選擇最大的一個時間復雜度:O(nlog2n)貪心先考慮只有兩個約數(shù)的數(shù)中最大的一個,如果沒有,再考慮38上界集合中每個數(shù)一個點,a/b是素數(shù),則連一條邊a->b,則數(shù)a是數(shù)b的倍數(shù)當且僅當a到b有有向道路.這樣構(gòu)圖的好處是邊比較少結(jié)論:如果a可選,則a出發(fā)一定有邊.證明:如果a出發(fā)的邊都不存在了，則根據(jù)游戲規(guī)則它的所有后代都將被刪除,與a可選矛盾.最好情況:每次只被動刪除一個數(shù)上界集合中每個數(shù)一個點,a/b是素數(shù),則連一條邊a->b39匹配每條邊a->b的權(quán)是a,則“每次選一個數(shù)刪一個數(shù)”的最大得分是圖的最大權(quán)匹配結(jié)論：不考慮邊的方向，這個圖是二分圖證明：考慮每個數(shù)u的惟一分解式每條邊(u,v)滿足u/v=p是素數(shù)，因此v的分解式中指數(shù)之和減1，奇偶性改變分解式中指數(shù)和為奇/偶的結(jié)點為X/Y結(jié)點匹配每條邊a->b的權(quán)是a,則“每次選一個數(shù)刪一個數(shù)”的最40匹配只是上界考慮以下匹配：a)2—22，b)3—39，c)11—33，d)13—26不難得出：a)在d)之前，d)在b)之前，b)在c)之前，c)在a)之前。而這是不可能實現(xiàn)的不過n比較小時匹配結(jié)果就是標準答案雖然如此,這個上界是相容的,可以用作IDA*算法的估價函數(shù)匹配只是上界考慮以下匹配：41不明智的選擇a至少有4個約數(shù)(包括自己),其中至少有一個比a的層次小2i)先刪b更好ii)先刪c更好iii)不會出現(xiàn)(設b/c=p1,b/d=p2,則a/p1和a/p2分別是c和d的倍數(shù),故沒刪除.但它們應和b同層)bacdbaabcd不明智的選擇a至少有4個約數(shù)(包括自己),其中至少有一個比42其他優(yōu)化檢查相鄰操作是否可交換猜想:存在一個數(shù)只有兩個約數(shù)沒有被刪除,并且這個數(shù)的所有倍數(shù)(除了它自己)已被刪除,那么刪除滿足條件的最大數(shù)是最優(yōu)的a2cabacab2abcb2cbcca2bac2bc2其他優(yōu)化檢查相鄰操作是否可交換a2cabacab2abcb243猜想的反例a,b,c是不同素數(shù),a<b<c,a2b<[n/2]貪心:方案先刪除,ab2,后面最大ac2+bc2更優(yōu)方案:先刪除ac2,再bc2,再abc但n<=120時反例不會出現(xiàn)a2cabacab2abcb2cbcca2bac2bc2猜想的反例a,b,c是不同素數(shù),a<b<c,a2b<[n/44運行結(jié)果如果不用猜想,則70~74,81~86,105~120都很慢用上猜想則所有數(shù)據(jù)0.5秒以內(nèi)出解N1030506580100105110120答案40301808132820413164343437644593運行結(jié)果如果不用猜想,則70~74,81~86,10545

結(jié)束語謝謝大家聆聽！??！46

結(jié)束語謝謝大家聆聽?。。?6二分圖匹配及其應用二分圖匹配及其應用目錄增廣路定理與Hall定理二分圖最大基數(shù)匹配二分圖最大權(quán)匹配應用目錄增廣路定理與Hall定理48最新二分圖匹配及其應用課件49最新二分圖匹配及其應用課件50最新二分圖匹配及其應用課件51最新二分圖匹配及其應用課件52最新二分圖匹配及其應用課件53最新二分圖匹配及其應用課件54Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要增廣次關(guān)鍵：用O(m)時間找一個極大最短增廣路集步驟1：用距離標號擴展匈牙利樹，找到第一個未蓋點時并不停止，把此時的距離標號設為上限。這樣，找到的所有未蓋點距離標號都相同步驟2：每次任取一個未蓋點，用DFS找到它到起點的增廣路(只沿著距離標號下降的方向),標記經(jīng)過的點,找所有增廣路的總時間為O(m)Hopcroft算法可以證明：如果每次找到的最短增廣路集是極55基于DFS的算法從貪心匹配,而不是空匹配開始每次從一個未蓋點開始DFS找增廣路,而不是一次性把所有未蓋點放入隊列進行BFS如果從一個未蓋點u開始找不到增廣路,則以后再也不用考慮u了.為什么?定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配的增廣路基于DFS的算法從貪心匹配,而不是空匹配開始56定理的證明(1)定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配M’的增廣路證明:假設增廣后從u出發(fā)有增廣路Q.若Q與P不相交,則Q就是M-增廣路,矛盾.因此Q與P相交.下面借助P和Q構(gòu)造出從u出發(fā)關(guān)于M的增廣路,從而得到矛盾定理的證明(1)定理:假設G的匹配為M,不存在從非飽和點57定理的證明(2)Q與P相交.設P的兩個M-非飽和點為u0和v0,而Q的兩個M’-非飽和點是u,v.從u開始沿Q走,設第一個P中結(jié)點為w,則w把P分為兩段,其中必有一段以M中邊與w關(guān)聯(lián),得到從u出發(fā)增廣路wv0u0vuPQ定理的證明(2)Q與P相交.設P的兩個M-非飽和點為u0和58完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個非負整數(shù)權(quán)值目標：求出權(quán)和最大的完美匹配特點：完美匹配容易求，但權(quán)最大的不易可行頂標：結(jié)點函數(shù)l，對任意弧(x,y)滿足相等子圖：G的生成子圖，包含所有點，但只包含滿足l(x)+l(y)=w(x,y)的所有弧(x,y)完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個非負整數(shù)權(quán)59相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)匹配證明：設M*是相等子圖的完美匹配，則根據(jù)定義設M是原圖的任意完美匹配，則關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)60算法思想關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配思想：隨便構(gòu)造一個可行頂標（例如Y結(jié)點頂標為0，X結(jié)點的頂標為它出發(fā)所有弧的最大權(quán)值，然后求相等子圖的最大匹配存在完美匹配，算法終止否則修改頂標使得相等子圖的邊變多，有更大機會存在完美匹配考慮相等子圖不存在完美匹配時的情形算法思想關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配61Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為6，不是完美匹配算法在尋找增廣路失敗的同時得到了一棵匈牙利樹雖然此匈牙利樹并沒有包含未蓋點（因此沒有找到增廣路），但仍然含有重要信息Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為62Kuhn-Munkres算法設匈牙利樹中的X結(jié)點集為S，Y結(jié)點集為T，則S到T沒有邊（否則匈牙利樹可以繼續(xù)生長）S到T的邊都是非匹配邊（想一想，為什么）但若把S中所有點的頂標同時減少一個相同整數(shù)a，則S到T中可能會有新邊進入相等子圖SSTTKuhn-Munkres算法設匈牙利樹中的X結(jié)點集為S，Y結(jié)63Kuhn-Munkres算法把S中所有點的頂標同時減少一個相同整數(shù)a，則S到T中可能會有新邊進入相等子圖為了保證S-T的匹配邊不離開相等子圖，把T中所有點的頂標同時增加aSSTT-a+a為保證有新邊進入，取如果S中每個頂標的實際減小值比這個值小則不會有新邊進入；如果比這個值大則頂標將變得不可行Kuhn-Munkres算法把S中所有點的頂標同時減少一個相64Kuhn-Munkres算法設邊(x,y)進入相同子圖y是未蓋點，則找到增廣路y和S中的點z匹配，則把z和y分別加入S和T中每次修改頂標要么找到增廣路，要么使匈牙利樹增加兩個結(jié)點因此一共需要O(n2)次修改頂標操作關(guān)鍵：快速修改頂標SSTT-a+aKuhn-Munkres算法設邊(x,y)進入相同子圖SST65頂標的修改方法1：枚舉S和T中的每個元素，根據(jù)定義計算最小值，每次修改的時間為O(n2)，總O(n4)方法2：對于T中的每個元素y，定義松弛量則a的計算公式變?yōu)轫敇说男薷姆椒?：枚舉S和T中的每個元素，根據(jù)定義計算最小值66頂標的快速修改每次增廣后用O(n2)時間計算所有點的初始slack，由于每次生長匈牙利樹時所有S-T弧的增量相同，因此修改每個slack值只需要常數(shù)時間，計算所有slack值需要O(n)時間每次增廣后最多修改n次頂標，因此每次增廣后修改頂標總時間降為O(n2)，總O(n3)結(jié)論：Kuhn-Munkres算法的總時間復雜度為O(n3)頂標的快速修改每次增廣后用O(n2)時間計算所有點的初始sl67例題1.BelovedSons(SGU210)國王有N個兒子，另外有N漂亮的女孩，每個兒子喜歡其中的某些。國王對每個兒子有一個喜愛程度。要把王子和這些女孩配對（不一定完全配對），使得所有被配對的王子被喜愛程度值的平方和盡可能大。例題1.BelovedSons(SGU210)國王有N68分析可以用二分圖的最佳匹配因為這個圖有特殊性，男孩子一邊任一個點連出的所有邊的權(quán)值都是相同的，所以只要將男孩子按照國王的喜歡程度從大到小排序，先對國王更喜歡的孩子擴展增廣路徑，就可以得到最優(yōu)解。這是為什么呢？分析可以用二分圖的最佳匹配69分析由增廣路的性質(zhì)可以知道一條增廣路的應用只可能在匹配的男孩子中加入一個人，而不可能刪去任意一個人。所以國王喜歡程度較低的男孩子進入匹配不可能對喜歡程度較高的孩子是否在匹配中產(chǎn)生任何影響：這就是貪心算法成立的原因。分析由增廣路的性質(zhì)可以知道一條增廣路的應用只可能在匹配的男孩70例題2.Dominoes(SGU190)給定一個N×N的棋盤，其中有一些格子被移除。要求在剩下的棋盤中放置互不重疊的1×2的骨牌，將棋盤蓋滿。例題2.Dominoes(SGU190)給定一個N×N的棋71分析將棋盤黑白染色，使得黑格周圍都是白格，白格周圍都是黑格。黑白格構(gòu)成了二分圖的兩個頂點集合，相鄰的格子之間有邊。這樣，二分圖的完備匹配就是問題的解了。實際上不需要單獨建立二分圖，直接在圖上操作即可。點和邊都是O(N2)個,因此時間復雜度為O(N3)分析將棋盤黑白染色，使得黑格周圍都是白格，白格周圍都是黑格。72例題3.Speleology(POI9906)一個山上有一個很大的洞，其中有n個室，編號為1~n，室與室之間有通道。編號越大的室在越下方。有一批洞穴學者要從編號為1的室走到編號為n的室中，途中他們只能從編號小的地方走到編號大的地方。每條和1或n相連的通道只允許一個人通過。問：最多可以有多少名洞穴學者？例題3.Speleology(POI9906)一個山上有一73分析我們可以把n個室看作n個點，把通道看作是點到點之間的一條有向邊。那么本題就是一個典型的網(wǎng)絡流問題。其中，每條和1或n相連的邊容量為1,其他邊容量為無窮大。1為源點，n為匯點。這個網(wǎng)絡的最大流即為問題的解其實這個圖是特殊的,考慮1出發(fā)直接可達集合S和直接可達n的集合T之間的最大匹配分析我們可以把n個室看作n個點，把通道看作是點到點之間的一74例題4.UnstableSystems(SGU218)求一個完備匹配，使得匹配邊中權(quán)值最大的邊權(quán)值最小。例題4.UnstableSystems(SGU218)求75分析算法一二分選擇flow，并且進行最大匹配算法二從權(quán)值最低的邊開始，每次增加一條邊。維護交錯樹森林，最多只可能增加一個交錯軌。因為找到N條交錯軌即可，而維護交錯樹森林的平攤復雜度為O(1)，所以總時間復雜度依然為O(N3)分析算法一76例題5.GreedyIsland(ZOJ1638)有n(<=10,000)種卡片，每種卡片上有三種屬性：攻擊、防御、超能力從n張卡片中選A張作為攻擊卡片，B張作為防御卡片，C張作為超能力卡片(A+B+C<=100)。要求攻擊卡片的總攻擊值、防御卡片的總防御值和超能力卡片的總超能力值之和盡量大例題5.GreedyIsland(ZOJ1638)有n77分析令A+B+C=m，則m<=100如果一張卡片被選為攻擊卡片，則它的攻擊值不可能排不到前m位（這樣前m位肯定有沒選的，換成它則提高攻擊值）這樣，只需要保留攻擊、防御和超能力各前100名，一共最多3m張（有重復的話比這個少）。分析令A+B+C=m，則m<=10078分析算法一：構(gòu)造二分圖，左邊3個點，表示攻擊、防御、超能力三個用途；右邊3m個點，表示所有需要考慮的卡片，則時間復雜度為O(m3)。算法二：左邊只有3個點，因此可以設d[i,a,b,c]表示前i張選了a張攻擊卡片，b張防御卡片，c張超能力卡片，則狀態(tài)轉(zhuǎn)移是O(1)的（考慮下一張卡片的四種決策），狀態(tài)不超過m4/9個，仍然高效分析算法一：構(gòu)造二分圖，左邊3個點，表示攻擊、防御、超能力三79例題6.DivideandConquer(SGU229)N*N的方格上有一些格子著黑色.把它們分成兩部分,使得其中一部分逆時針旋轉(zhuǎn)90度、180度或270度后再平移,可以和另一部分重合例題6.DivideandConquer(SGU22980分析枚舉旋轉(zhuǎn)角度和平移向量,枚舉量O(n2)每個點變換后有一個唯一的象.對于每個黑點p,如果它的象也是黑點,則連一條有向邊則問題有解當且僅當此圖有完美匹配如果得到的圖有度數(shù)為0的點或者自環(huán),顯然沒有匹配,否則圖是鏈和環(huán)的集合,各個連通分量很容易求出各自的最大匹配時間復雜度為:O(n4)分析枚舉旋轉(zhuǎn)角度和平移向量,枚舉量O(n2)81例題7.整數(shù)因子團問題給整數(shù)n,考慮集合{1,2,…,n}.每次可以選擇集合中的一個元素k,刪除它和它在集合中的所有因子,要求每次至少刪除兩個數(shù)(即k至少有一個小于k的約數(shù)在集合中)例如,n=6時方案一:依次選5,6,剩余序列為4方案二:依次選5,4,6,剩余序列為空輸入n(<=120),求一種方案讓選擇的數(shù)之和盡量大.注意選擇的數(shù)并不等同于刪除的數(shù)例題7.整數(shù)因子團問題給整數(shù)n,考慮集合{1,2,…82分析似乎并沒有很好的方法,搜索吧下界:一個不錯的解,先貪心,搜索過程中不斷改進為當前得到的最優(yōu)解上界:對當前狀態(tài)的估計,應被設計為狀態(tài)的函數(shù).因為頻繁調(diào)用,計算量不應太大關(guān)鍵:最優(yōu)性剪枝當前分數(shù)+當前狀態(tài)的上界<=下界分析似乎并沒有很好的方法,搜索吧83貪心先考慮只有兩個約數(shù)的數(shù)中最大的一個,如果沒有,再考慮只有三個約數(shù)的數(shù)中最大的一個.只有一種情況例外:如果q有一個倍數(shù)p,使得邊p->q存在且p出發(fā)只有一條邊.刪除q會讓p沒有辦法刪除,還不如主動選擇p,效果是一樣的.如果有多個p,顯然應選擇最大的一個時間復雜度:O(nlog2n)貪心先考慮只有