圖論常見模型與分析

1、圖論常見模型與思想1強連通分量相關(guān)概念：有向圖的強連通分量(SCC)是指，對于強連通分量里面的任意兩個點u,v，都存在從u到v的路和從v到u的路算法：復雜度均為O(V+E)Kosaraju (兩次dfs)Tarjan / Gabow (一次dfs)2Tarjan對圖進行DFS，每個SCC都是DFS樹的一個子樹。在搜索時用堆棧維護當前正在處理的結(jié)點，棧頂?shù)娜舾稍丶唇M成一個SCC。類似求割點的過程，定義Lowu = min(dfnu, lowv, (u,v)為樹邊dfnv, (u,v)為后向邊 )若對某點u有 dfnu = lowu，說明以u為根的子樹上的點為一個SCC3tarjan(u) DF

2、Nu=Lowu=+Index / 為u設定dfn和Low初值 Stack.push(u) / 將節(jié)點u壓入棧中for each (u, v) in E / 枚舉每一條邊 if (v is not visted) / 如果節(jié)點v未被訪問過(樹邊)tarjan(v) / 繼續(xù)向下找 Lowu = min(Lowu, Lowv) else if (v in S) / 如果節(jié)點u還在棧內(nèi)(后向邊)Lowu = min(Lowu, DFNv) if (DFNu = Lowu) / 節(jié)點u是SCC的根repeat v = S.pop / 將v退棧，為該SCC中一個頂點print v until (u= v

3、) 45678強連通分量相關(guān)關(guān)鍵點：一個強連通分量內(nèi)部的所有點，在某種意義上是“等價”的。圖中的邊存在某種意義上的“傳遞性”。通過縮點操作可以把復雜的一般有向圖轉(zhuǎn)化為DAG，使得問題簡化9例題分析Popular Cows (USACO Fall 03)POJ 2186N頭奶牛，給出若干個歡迎關(guān)系A B，表示A歡迎B，歡迎關(guān)系是單向的，但是是可以傳遞的。另外每個奶牛都是歡迎他自己的。求出被所有的奶牛歡迎的奶牛的數(shù)目。奶牛數(shù)目N10000直接的歡迎關(guān)系數(shù)目M5000010例題分析如果A歡迎B，就連一條從A到B的有向邊容易發(fā)現(xiàn)，在同一個強連通分量里的點具有同樣的“受歡迎程度”：能夠到達它們的點集是相

4、同的，從它們出發(fā)能夠到達的點集也是相同的。我們求出原圖的強連通分量，然后收縮11例題分析容易發(fā)現(xiàn)，新圖中唯一的出度為0的點即為所求。因為新圖不含有環(huán)，這樣的點一定存在。如果出度為0的點不唯一則無解。時間復雜度 O(E)12例題分析WTommys Trouble(TOJ2233/TOI 1135)WTommy需要向所有人通知某件事情，因為人數(shù)眾多，他想出了一個省力的方法：他只通知隊中的某些人，然后讓這些人去通知所有他們認識的人，這些新被通知的人又去通知更多的人直到最后隊中的所有人都被通知到。給定最初時WTommy通知每個人所需的花費，現(xiàn)在他想求出一種方案，使得花費最少，并且保證最終所有人都能被通

5、知到。13例題分析Input4 330 20 10 401 22 12 3Output : 601 N 10000, 0 M 200000 14例題分析同一個強連通分量里，只要有一人被通知即可縮點后得到的DAG中，如果一個點被通知，則它的所有后繼結(jié)點都會被通知。故只需通知入度為0的點在入度為0的每個點所表示的連通分量中，通知花費最少的那個人，即為最優(yōu)解O(E)15例題分析NOIP 2009 最優(yōu)貿(mào)易(Trade)C 國有 n 個大城市和 m 條道路（單向或雙向），每條道路連接這 n 個城市中的某兩個城市。水晶球在各地有不同的價格。某商人準備從1走到n（任何城市可以經(jīng)過多次），在某個城市買入，并

6、在另一城市賣出，收益即為價格之差。他最多只買入和賣出1次，求最大收益。16例題分析如下圖，五城市水晶球價格分別為 4，3，5，6，1 。則最高的方案是14545。在第一次到5時買入，第二次到4時賣出，收益為6 1 = 5 17例題分析若圖中無環(huán)，則可以DP求解：設vi表示i點的物品價格。令dpi表示從i到N的路徑中的最高價格。若從i點買入，則收益為dpi-vi。最終結(jié)果即為max(dpi-vi)狀態(tài)轉(zhuǎn)移方程：dpi = max(vi, maxdpj, 當ij有邊時)注意：應排除不能到達N的點18例題分析若圖中有環(huán)在同一SCC里的全部點的“連通性”是等價的：能夠到達它們的點集是相同的，從它們出發(fā)

7、能夠到達的點集也是相同的。若從此SCC買入，則一定買價格最低的點若從此SCC賣出，則一定買價格最高的點19例題分析最終解法：對原圖求SCC并縮點，設新點i中最高價格點為Hi，最低價格點為Li。在新的DAG圖上有DP：dpi = max(Hi, maxdpj, 當ij有邊時)最終結(jié)果為maxdpi Li注意：應排除不能到達N的點20例題分析Poly-time Reductions(Hefei 2008)給定一個有向圖G，求一個包含最少邊的有向圖G，使G和G的傳遞閉包相同。圖的傳遞閉包是指，若存在邊AB, BC，則必存在邊ACN = 100, M = 1000021例題分析Input 3 31 2

8、2 31 3Output2Input4 61 22 12 33 23 44 3Output422例題分析求強連通分量，縮點在同一強連通分量內(nèi)部，最少需要幾條邊？不同分量之間的邊，有哪一種是不必要的？23例題分析先求傳遞閉包對于邊(u,v)，若存在一點k，使得uk且kv，則邊(u,v)是不必要的易得一個O(n3)的算法證明？24路徑覆蓋相關(guān)經(jīng)典模型：給定一有向無環(huán)圖，要求用最少的不相交路徑把所有點覆蓋上解法：把原圖中的每個點i拆為兩個，分別屬于X集和Y集。對于原圖中的有向邊(i，j)，在新圖中添加邊(Xi, Yj)，得到一個二分圖。最小路徑覆蓋數(shù) = 原圖頂點數(shù) 新圖最大匹配數(shù)“拆點”思路廣泛應

9、用于此類問題25路徑覆蓋相關(guān)簡單解釋：原圖的路徑覆蓋和新圖的匹配間有對應關(guān)系：每條覆蓋邊都是匹配中的一條邊，且只有路徑的最后一個點沒有被匹配上。路徑要求不能相交，恰好對應于匹配中兩匹配邊不能有公共端點。于是求最大匹配后，不能被匹配上的點，即是路徑的最后一個點。有多少個不能被匹配的點，就有多少條路徑存在。路徑數(shù)=原點數(shù)匹配邊數(shù)。因此我們使匹配邊數(shù)最大，即是使路徑數(shù)最小。26例題分析Hanoi Tower Troubles Again! (OIBH Contest)ZOJ 1239題目大意：給定柱子數(shù)N，按編號從小到大放球，要求：如果該球不在最底數(shù)，則該球和它下面一個球的編號之和必須為完全平方數(shù)。

10、問對于給定的N，最多能放多少球上去。N=5027例題分析28例題分析考慮一下相關(guān)的問題：給k個球，問最少需要多少個柱子才能把它們都放上?如果能解出上述問題，則二分k值即可求解原問題。繼續(xù)類比球?, 柱子?29例題分析如果a+b是完全平方數(shù)(ab)，那么我們連一條有向邊(a,b)于是，問題變成了求DAG的最小路徑覆蓋。因為連邊時保證ab，所以無環(huán)路徑柱子路徑不相交同一個球不能用兩次30例題分析POJ Monthly / POJ 3216題目大意：城市有Q個城區(qū)，有些城區(qū)之間有路連接，經(jīng)過這些路所需時間已知?，F(xiàn)在有M個維修任務要進行，已知每個任務的地點、deadline和完成每個任務所需時間。維修

11、工可以從任何一個城區(qū)開始，完成任務后可以到另一個城區(qū)繼續(xù)。問至少要派出多少個維修工才能及時任務。(Q=20, M=200)31例題分析Sample Input1 20 1 1 10 1 5 10 Sample Output232例題分析Floyd預處理所有點對間最短路徑dis設有任務a,b，如果在完成任務a后還來得及走到b處繼續(xù)，即deadlinea + cost + disab = deadlineb，則連一條有向邊(a,b)33例題分析由建圖的過程知，這個有向圖中一定不會出現(xiàn)環(huán)于是問題轉(zhuǎn)化為DAG的最小路徑覆蓋經(jīng)典問題，(點數(shù)-最大匹配數(shù))即為最終結(jié)果。34Dilworth定理NOIP 1

12、999 導彈攔截導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。給定依次飛來的導彈高度，問(1)一套系統(tǒng)最多攔截多少導彈 (2)攔截所有導彈最少需要幾套系統(tǒng)35Dilworth定理第一問是簡單的最長不上升子序列O(nlogn)第二問解法一：最小路徑覆蓋 (復雜度過高)解法二：貪心? 36Dilworth定理偏序關(guān)系：定義在集合X上的二元關(guān)系，對X中任意元素a,b,c滿足三條性質(zhì)：1. 自反性：aa2. 反對稱性：若ab且ba，則a=b3. 傳遞性：若ab且bc，則ac對于X中任意兩元素a,b，若有ab或ba，則稱a和b是可比的，否則為不可

13、比。37Dilworth定理一個鏈C是X的一個子集，它的任意兩個元素都可比。 一個反鏈A是X的一個子集，它的任意兩個元素都不能進行比較。Dilworth定理： 最大反鏈的大小 = 最少可劃分成的鏈的數(shù)目38Dilworth定理若在攔截導彈a以后還能攔截導彈b，則認為存在關(guān)系ab（易得此為偏序關(guān)系）問題一：求最大鏈問題二：求最少劃分成多少個鏈。由Dilworth定理，等價于求最大的反鏈在此處，最大的反鏈，即最長上升子序列O(nlogn)39Dilworth定理思考：能用dilworth定理解決的問題一定能用路徑覆蓋解決嗎？反之是否成立？什么情況下只能用匹配來做？40Dilworth定理HDU 3

14、335 Divisibility給定n個數(shù)(n1 ?45廣義的路徑覆蓋類比K=1的情況，不同之處在于，每個左邊的點可以匹配多個右邊的點，于是把每個點i拆成兩個點i和i若i能吃掉j，連邊(ij)，容量為1從源點到每個左側(cè)點i連邊，容量為K從每個右側(cè)點i到匯點連邊，容量為1求最大流F，則n-F即為所求46廣義的路徑覆蓋對于屬性完全相同的細菌，因為是完全等價，我們可以任意設定一個順序，例如，以在輸入數(shù)據(jù)中出現(xiàn)的先后順序為序，只允許排前面的細菌吃掉排后面的細菌。47SPOJ TOURS有N個城市M條單向道路，道路有長度權(quán)值。要求設計出若干條環(huán)線，使得每個城市都屬于（且僅屬于）一條環(huán)線。每條環(huán)線最少包含

15、兩個城市，且經(jīng)過每個城市最多一次。要求所有環(huán)線的總長度之和最小。N = 20048SPOJ TOURSInput:5 81 2 42 1 71 3 103 2 103 4 104 5 105 3 105 4 3 Output:40兩條環(huán)線：1 3 2 15 4 549廣義的路徑覆蓋思考：環(huán)覆蓋？與路徑覆蓋有何區(qū)別與聯(lián)系？可否借用類似的思路？50廣義的路徑覆蓋把每個點拆成兩個點，按同樣方法得到二分圖，我們發(fā)現(xiàn)一個環(huán)覆蓋的方案恰好對應一個完美匹配。于是原問題轉(zhuǎn)化為二分圖帶權(quán)匹配。思考：此方法能否用來解決Hamilton回路問題或TSP問題？51例題分析TC SRM 435 Level 3題目大意是

16、，某公司計劃重組管理結(jié)構(gòu)，使所有人員形成一個“森林”狀結(jié)構(gòu)，即若干樹的集合，每個人只屬于一棵樹，也就是每個人至多有一個上司，要求樹的個數(shù)盡可能少。這個公司在之前曾有過一些暫時管理關(guān)系，比如A曾經(jīng)暫時管理過B，B可能也暫時管理過A。如果A暫時管理過B，那么A就認為他比B優(yōu)秀，而且這種優(yōu)越感是可傳遞的，即如果A管理過B，B管理過C，則A也認為他比C優(yōu)秀。如果A認為自己比B優(yōu)秀，B也認為自己比A優(yōu)秀，就說兩個人有“互斥優(yōu)越感”。52例題分析現(xiàn)在要求重組后得到的森林狀結(jié)構(gòu)滿足：1. 任何人的下屬應該是他曾經(jīng)管理過的人。2. 不應有任何人認為他比自己的直接上司優(yōu)秀。3. 有“互斥優(yōu)越感”的人不應當有同一

17、個上司。復雜的條件，奇怪的約束，如何下手？_53例題分析Ans = 1 Ans = 1 Ans = 430123012301254例題分析如果A曾經(jīng)管理B，我們就連有向邊(A, B)，那么“互斥優(yōu)越感”這個東西很容易讓人想到強連通分量，一個SCC內(nèi)部的所有人都是互斥的。我們首先考慮每個SCC只有一個點的情況，這時候圖是一個有向無環(huán)圖(DAG)，類比DAG上的最小路徑覆蓋問題，這題我們求的是“最小樹覆蓋”55例題分析在一個“樹覆蓋”里，除了根，所有的點都有一個入邊。我們要使盡可能多的點有一個入邊，且不破壞條件3，即同一個連通分量中所有的點的“父親”是不同的點。56例題分析對每個SCC作匹配，左邊

18、是SCC外的點，右邊是SCC內(nèi)的點，求最大匹配，剩下的沒被匹配上的右邊的點就不得不做為根所有SCC里沒匹配上的點的總和即為所求57二分圖交錯增廣路相關(guān)交錯增廣路是求二分圖時的一個概念表示從左側(cè)X集開始，交替經(jīng)過 未匹配邊 已匹配邊 未匹配邊 已匹配邊 未匹配邊 的過程。若交錯路的兩端均為未匹配邊，說明找到一條可增廣路（此時必停在右側(cè)Y集），此時可以通過交換匹配邊和未匹配邊，使匹配數(shù)+158NOI 2009 TransformN = 10000Sample Input: 51 1 2 2 1Sample Output: 1 2 4 0 359NOI 2009 Transform建立二分圖，左右各

19、有N個點，若i點經(jīng)變換后可能到達j，則在左邊的i和右邊的j之間相邊。問題即為求此圖的字典序最小的完美匹配60NOI 2009 Transform如何保證字典序最??？方法一：依次窮舉由題意知每個左邊點最多與兩個右邊點相連。從0點開始，假設0點與右邊兩點中較小點相連，檢驗剩下圖是否仍有完美匹配。若無，則說明0應連另一點。對1點,2點繼續(xù)此過程。復雜度O(n3)61NOI 2009 Transform方法二：調(diào)整首先求一個完美匹配。然后從左邊編號最小的點開始，依次判斷每個頂點的對應。如果當前頂點對應的點是序號較小頂點，可以直接取得，否則嘗試修正。修正的方法是強制將當前頂點對應到另一個序號較小頂點，這必然導致X集合中另一個頂點失配，此時從該頂點開始嘗試找一條增廣路，如果存在則修正成功，否則修正失敗，撤回操作。 復雜度O(n2)62NOI 2009 Transform方法三：貪心Step1. 對于左邊或右邊度為1的點，其匹配方式是唯一確定的?？梢詫⑵湟来未_定并將對應的邊刪除，這樣可能再次出現(xiàn)度為1的點，重復此過程直至不能繼續(xù)。Step2