圖論常見(jiàn)模型與分析

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

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

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

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

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

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

7、能夠到達(dá)的點(diǎn)集也是相同的。若從此SCC買入，則一定買價(jià)格最低的點(diǎn)若從此SCC賣出，則一定買價(jià)格最高的點(diǎn)19例題分析最終解法：對(duì)原圖求SCC并縮點(diǎn)，設(shè)新點(diǎn)i中最高價(jià)格點(diǎn)為Hi，最低價(jià)格點(diǎn)為L(zhǎng)i。在新的DAG圖上有DP：dpi = max(Hi, maxdpj, 當(dāng)ij有邊時(shí))最終結(jié)果為maxdpi Li注意：應(yīng)排除不能到達(dá)N的點(diǎn)20例題分析Poly-time Reductions(Hefei 2008)給定一個(gè)有向圖G，求一個(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例題分析求強(qiáng)連通分量，縮點(diǎn)在同一強(qiáng)連通分量?jī)?nèi)部，最少需要幾條邊？不同分量之間的邊，有哪一種是不必要的？23例題分析先求傳遞閉包對(duì)于邊(u,v)，若存在一點(diǎn)k，使得uk且kv，則邊(u,v)是不必要的易得一個(gè)O(n3)的算法證明？24路徑覆蓋相關(guān)經(jīng)典模型：給定一有向無(wú)環(huán)圖，要求用最少的不相交路徑把所有點(diǎn)覆蓋上解法：把原圖中的每個(gè)點(diǎn)i拆為兩個(gè)，分別屬于X集和Y集。對(duì)于原圖中的有向邊(i，j)，在新圖中添加邊(Xi, Yj)，得到一個(gè)二分圖。最小路徑覆蓋數(shù) = 原圖頂點(diǎn)數(shù) 新圖最大匹配數(shù)“拆點(diǎn)”思路廣泛應(yīng)

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

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

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

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

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

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

15、兩個(gè)城市，且經(jīng)過(guò)每個(gè)城市最多一次。要求所有環(huán)線的總長(zhǎng)度之和最小。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廣義的路徑覆蓋把每個(gè)點(diǎn)拆成兩個(gè)點(diǎn)，按同樣方法得到二分圖，我們發(fā)現(xiàn)一個(gè)環(huán)覆蓋的方案恰好對(duì)應(yīng)一個(gè)完美匹配。于是原問(wèn)題轉(zhuǎn)化為二分圖帶權(quán)匹配。思考：此方法能否用來(lái)解決Hamilton回路問(wèn)題或TSP問(wèn)題？51例題分析TC SRM 435 Level 3題目大意是

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

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

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

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