圖論劉汝佳課件

目錄DFS相關(guān)算法二分圖相關(guān)算法網(wǎng)絡流相關(guān)算法最小樹形圖目錄DFS相關(guān)算法1DFS相關(guān)算法DFS相關(guān)算法2基本應用找連通分量二分圖判定無向圖的連通性有向圖的連通性基本應用找連通分量3時間戳和邊分類時間初始化為0，最大值為2|E|。數(shù)值本身無意義，但大小關(guān)系有意義voidPREVISIT(intu){pre[u]=++dfs_clock;}voidPOSTVISIT(intu){post[u]=++dfs_clock;}無向圖：只有樹邊和反向邊時間戳和邊分類時間初始化為0，最大值為2|E|。數(shù)值本身無意4無向連通圖的割頂DFS森林一定只有一棵樹。樹根是不是割頂呢？不難發(fā)現(xiàn)，當且僅當它有兩個或更多的兒子時，它才是割頂——無向圖只有樹邊和反向邊，不存在跨越兩棵子樹的邊。對于其他點，情況就要復雜一些。我們有下面的定理：定理：在無向連通圖G的DFS樹中，非根結(jié)點u是G的割頂當且僅當u存在一個兒子w，使得w及其所有后代都沒有反向邊連回u的祖先（連回u不算）。無向連通圖的割頂DFS森林一定只有一棵樹。樹根是不是割頂呢？5定理的證明u存在一個兒子w，使得w及其所有后代都沒有反向邊連回u的祖先（連回u不算）。定理的證明u存在一個兒子w，使得w及其所有后代都沒有反向邊連6為了方便起見，我們設low(u)為u及其后代所能連回的最早的祖先的pre值，則定理中的條件就可以簡寫成：結(jié)點u存在一個兒子w，使得low(w)>=pre(u)。若low(w)>pre(u)，即w最多只能連回自己，則只需刪除(u,w)一條邊就可以讓圖G非連通了。滿足這個條件的邊稱為橋（bridge）為了方便起見，我們設low(u)為u及其后代所能連回的最早的7low函數(shù)本身的計算voiddfs(intu,intfa){//u的父親結(jié)點是fa，初次調(diào)用fa=-1low[u]=pre[u]=++dfs_clock;//初始化low(u)intd=G[u].size();for(inti=0;i<d;i++){//枚舉每條邊(u,w)intw=G[u][i];if(!pre[w]){//沒有訪問過點v（所有pre值初始化為0）dfs(w,u);//w的父親結(jié)點是ulow[u]=min(low[u],low[w]);//用后代的low函數(shù)更新}elseif(w!=fa)low[u]=min(low[u],pre[w]);//用反向邊更新}}low函數(shù)本身的計算voiddfs(intu,int8雙連通與邊-雙連通如果一個無向連通圖沒有割頂，稱它是點-雙連通的，一般簡稱雙連通（biconnected）；如果沒有橋，稱它是邊-雙連通（edge-biconnected）的。點-雙連通的等價條件：任意兩點存在兩條“點不重復”的路徑。這個要求等價于任意兩條邊都在同一個簡單環(huán)中，因此內(nèi)部無割頂。邊-雙連通的等價條件：任意兩點存在兩條“邊不重復”的路徑。這個要求要低一點，只需要每條邊都至少在一個簡單環(huán)中，因此所有邊都不是橋。雙連通與邊-雙連通如果一個無向連通圖沒有割頂，稱它是點-雙連9點/邊-雙連通分量下圖有兩個點-雙連通分量：{1,2,3}和{3,4,5}，但只有一個邊-雙連通分量：{1,2,3,4,5}。點/邊-雙連通分量下圖有兩個點-雙連通分量：{1,2,3}和10算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次dfs染色。因為邊-雙連通分量是沒有公共頂點的，所以只要在第二次dfs的時候保證不經(jīng)過橋即可。點-雙連通分量：Tarjan算法（見后）算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次dfs11voiddfs(intu,intfa){low[u]=pre[u]=++dfs_clock;intd=G[u].size();for(inti=0;i<d;i++){intw=G[u][i];

//求BCC用.每遇到一條邊(u,w)都要加到棧中，不管w是否已編號if(ins[u][w])continue;ins[u][w]=ins[w][u]=1;S.push(mp(u,w));

if(!pre[w]){dfs(w,u);low[u]=min(low[u],low[w]);if(low[w]>=pre[u]){//u是割頂或者根，意味著一個bcc的終止++bcc_cnt;printf("BCC%d,containing(%d,%d):\n",bcc_cnt,u,w);pair<int,int>e;do{e=S.top();S.pop();printf("%d%d\n",e.first,e.second);}while(e!=mp(u,w));}}elseif(w!=fa)low[u]=min(low[u],pre[w]);}}voiddfs(intu,intfa){12有向圖的強連通分量理想情況：依次從I,C,D…出發(fā)DFS，則每次DFS恰好得到一個SCC有向圖的強連通分量理想情況：依次從I,C,D…出發(fā)DFS13Kosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)于各個SCC拓撲順序的有關(guān)信息，而第二次DFS按照這個拓撲順序的逆序進行DFS，從而把每個SCC分開。第一步：對G進行普通的DFS，把各個結(jié)點按照訪問結(jié)束時間從后往前的順序放入列表list中。第二步：計算G的轉(zhuǎn)置GT（即把所有有向邊(u,v)變?yōu)橛邢蜻?v,u)）第三步：對GT進行DFS，其中主循環(huán)中按下標從小到大的順序依次考慮list中的各個結(jié)點，則每次dfs將會得到一個不同的SCC。Kosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)14圓桌騎士每次圓桌會議由至少3個騎士參加，騎士的數(shù)目必須為奇數(shù)，且在圓桌旁坐下后相鄰騎士不能相互憎恨。統(tǒng)計有多少個騎士不可能參加任何一個會議。有n個騎士，m個相互憎恨的騎士對N<=1000,m<=1000000圓桌騎士每次圓桌會議由至少3個騎士參加，騎士的數(shù)目必須為奇數(shù)15以騎士作為頂點建立無向圖G。如果兩個騎士不相互憎恨，在他們之間連一條無向邊。則題目轉(zhuǎn)化為求不在任何一個奇圈上的頂點個數(shù)。如果圖G不連通，應對每個連通分量分別求解。下面假設圖G連通。假設結(jié)點v在某個奇圈上，則根據(jù)定義，該圈上的所有結(jié)點都屬于同一個點-雙連通分量。由于該雙連通分量中含有奇圈，它一定不是二分圖。反過來是否成立呢？即：如果結(jié)點v所屬的某一個雙連通分量B（因為v可能屬于多個雙連通分量）不是二分圖，v是否一定屬于一個奇圈呢？以騎士作為頂點建立無向圖G。如果兩個騎士不相互憎恨，在他們之16問題在于：盡管B不是二分圖意味著它一定包含一個奇圈C，這個C可能并不包含v。我們得想辦法讓v攙和進來。如圖，根據(jù)連通性，從v一定可以到達C中的某個結(jié)點u1；根據(jù)雙連通性，C中還應存在另一個結(jié)點u2，使得從v出發(fā)有兩條不相交路徑（除起點外無公共結(jié)點），分別到u1和u2。由于在C中，從u1到u2的兩條路的長度一奇一偶，總能構(gòu)造出一條經(jīng)過v的奇圈。主算法：對于每個連通分量的每個雙連通分量B，若它不是二分圖，給B中所有結(jié)點標記為“在奇圈上”。問題在于：盡管B不是二分圖意味著它一定包含一個奇圈C，這個C17井下礦工有一座地下的稀有金屬礦由n條隧道和一些連接點組成，其中每條隧道連接兩個連接點。任意兩個連接點之間最多只有一條隧道。為了降低礦工的危險，你的任務是在一些連接點處安裝太平井和相應的逃生裝置，使得不管哪個連接點倒塌，不在此連接點的所有礦工都能到達太平井逃生（假定除倒塌的連接點不能通行外，其他隧道和連接點完好無損）。為了節(jié)約成本，你應當在盡量少的連接點安裝太平井。你還需要計算出在太平井的數(shù)目最小時的安裝方案總數(shù)。井下礦工有一座地下的稀有金屬礦由n條隧道和一些連接點組成，其18本題的模型是：把一個無向圖上選擇盡量少的點涂黑（對應太平井），使得任意刪除一個點后，每個連通分量至少有一個黑點。不難發(fā)現(xiàn)，把割頂涂黑是不劃算的，而且在同一個點-雙連通分量中圖兩個黑點也是不劃算的。進一步分析發(fā)現(xiàn)：如果把每個點-雙連通分量收縮成一個點，則整個圖會變成一棵樹。最優(yōu)方案是在樹的每個葉結(jié)點中選一個非割頂涂黑，兩個問題同時解決。一個特殊情況是整個圖沒有割頂。此時至少需要涂兩個點，方案總數(shù)是C(V,2)，其中V是連接點個數(shù)。本題的模型是：把一個無向圖上選擇盡量少的點涂黑（對應太平井）19等價性證明在數(shù)學中，我們常常需要完成若干個命題的等價性證明。比如，有四個命題a,b,c,d，我們證明ab，然后bc，最后cd。注意每次證明都是雙向的，因此一共完成了6次推導。另一種方法是證明ab，然后bc，接著cd，最后da，只需4次?，F(xiàn)在你的任務是證明n個命題全部等價，且你的朋友已經(jīng)為你作出了m次推導（已知每次推導的內(nèi)容），你至少還需要做幾次推導才能完成整個證明？n<=20000,m<=50000等價性證明在數(shù)學中，我們常常需要完成若干個命題的等價性證明。20分析用圖論術(shù)語來說，本題是給出n個結(jié)點m條邊的有向圖，要求填加盡量少的邊，使得新圖強連通。先找出強連通分量，然后把每個強連通分量縮成一個點，得到一個DAG接下來，設有a個結(jié)點（別忘了，這里的每個結(jié)點對應于原圖的一個強連通分量）的入度為0，b個結(jié)點的出度為0，則max{a,b}就是答案。注意特殊情況：當原圖已經(jīng)強連通時，答案是0而不是1。證明留給讀者。分析用圖論術(shù)語來說，本題是給出n個結(jié)點m條邊的有向圖，要求填21無向仙人掌仙人掌被定義為每個點最多在一個簡單（結(jié)點不重復經(jīng)過）回路上的連通無向圖。你的任務是計算一個無向圖的“仙人掌度”，即它有多少個生成子圖（包括自身）也是仙人掌。如果原圖不是仙人掌，輸出0無向仙人掌仙人掌被定義為每個點最多在一個簡單（結(jié)點不重復經(jīng)過22我們采用分析DFS樹的方法來尋求解決問題的方法。首先，對于一個節(jié)點u，如果它在DFS樹上的某個孩子v滿足low(v)<pre(u)，那么(u，parent(u))這條邊就必然在一個環(huán)上；同樣的，如果u能夠通過反向邊訪問到它的某個祖先節(jié)點w，那么(u，parent(u))這條邊就一定在另外一個環(huán)上。我們對于每個節(jié)點u記錄下這兩種情況發(fā)生的次數(shù)c(u)。如果c(u)>1，那么這個圖必然不是仙人掌，直接輸出0。我們采用分析DFS樹的方法來尋求解決問題的方法。首先，對于一23對于一個仙人掌，如果計算它的仙人掌度呢？顯然，對于一條不屬于任何一個環(huán)的邊，它一定是不可以刪去的，而對于一個長度為L的環(huán)，我們則有L+1種選擇（全部保留或者刪去其中的任意一條邊）。根據(jù)乘法原理，答案就是所有環(huán)長度加一后相乘的結(jié)果。因為所有的工作都可以在一次DFS之內(nèi)完成，所有整個算法的時間復雜度為O(m)。具體實現(xiàn)的時候有一點需要注意：為了避免棧溢出，最好不要在遞歸的同時計算答案。一種較好的方法是遞歸時只記錄每個環(huán)的長度，待全部處理完之后再進行高精度計算。對于一個仙人掌，如果計算它的仙人掌度呢？顯然，對于一條不屬于24二分圖最大匹配二分圖最大匹配25二分圖最大匹配二分圖：結(jié)點可以分為兩部分X和Y，每部分內(nèi)部無邊相連匹配：無公共點的邊集合未蓋點：不與任何匹配邊鄰接的點最大匹配：包含邊數(shù)最多的匹配XY二分圖最大匹配二分圖：結(jié)點可以分為兩部分X和Y，每部分內(nèi)部26交替路、增廣路從未蓋點開始經(jīng)過非匹配邊、匹配邊、非匹配邊……序列，最終通過一條非匹配邊到達另一個未蓋點非匹配邊個數(shù)比匹配邊個數(shù)多一如果把匹配邊和非匹配邊互換，匹配仍合法，但基數(shù)加一交替路、增廣路從未蓋點開始經(jīng)過非匹配邊、匹配邊、非匹配邊……27增廣路定理匹配是最大匹配當且僅當不存在增廣路這個定理適用于任意圖011001011010匈牙利樹思考：忽略虛線邊會導致存在增廣路卻找不到嗎？增廣路定理匹配是最大匹配當且僅當不存在增廣路這個定理適用于任28增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的對稱差G’,則G’在M’中的邊應比M’中更多.G’有三種可能的連通分支孤立點.當某邊(u,v)同時屬于兩個匹配,則u和v都是孤立點.交替回路.該回路中屬于M和M’的邊數(shù)相同交替道路.如果不存在增廣路,則|M’|=|M|,與假設矛盾;如果存在M關(guān)于M’的增廣路,又與M’是最大匹配矛盾,因此存在M’關(guān)于M的增廣路增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.29Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在完全匹配(X的結(jié)點全被匹配)的充要條件是對于X的任意子集A,恒有必要性.若存在A使得右邊>左邊,則A無法全部匹配充分性.假設G的最大匹配M不是完全匹配,一定存在結(jié)點X的結(jié)點x0關(guān)于M是非飽和點.如果x0的鄰集為空,則令A={x0}引出矛盾;如果非空則其中每個結(jié)點均為飽和點(否則會有增廣路).尋找與x0為端點的關(guān)于M的一切交錯路,設其中Y結(jié)點的集合為Y’,X結(jié)點的集合為X’,則Y’結(jié)點與X’-{x0}的結(jié)點一一對應,因此|X’|>|Y’|,令A=X’引出矛盾.Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在完全匹配(30二分圖最大匹配算法匈牙利樹是從所有未蓋點,而不是從固定未蓋點長出的樹Edmonds-Karp算法:把所有未蓋點放到隊列中,BFS尋找/增廣路時間均為O(m)最多找O(n)次時間復雜度O(nm)Hopcroft算法：每次沿多條增廣路同時增廣每次尋找若干條結(jié)點不相交最短增廣路每次的最短增廣路集是極大的時間復雜度基于DFS的算法:每次選一個未蓋點u進行DFS.如果找不到增廣路則換一個未蓋點,且以后再也不從u出發(fā)找增廣路.二分圖最大匹配算法匈牙利樹是從所有未蓋點,而不是從固定未蓋31Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要增廣次關(guān)鍵：用O(m)時間找一個極大最短增廣路集步驟1：用距離標號擴展匈牙利樹，找到第一個未蓋點時并不停止，把此時的距離標號設為上限。這樣，找到的所有未蓋點距離標號都相同步驟2：每次任取一個未蓋點，用DFS找到它到起點的增廣路(只沿著距離標號下降的方向),標記經(jīng)過的點,找所有增廣路的總時間為O(m)Hopcroft算法可以證明：如果每次找到的最短增廣路集是極32基于DFS的算法從貪心匹配,而不是空匹配開始每次從一個未蓋點開始DFS找增廣路,而不是一次性把所有未蓋點放入隊列進行BFS如果從一個未蓋點u開始找不到增廣路,則以后再也不用考慮u了.為什么?定理:假設G的匹配為M,不存在從非飽和點u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配的增廣路基于DFS的算法從貪心匹配,而不是空匹配開始33定理的證明(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,不存在從非飽和點34定理的證明(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和35應用舉例：最大最小匹配求一個完備匹配，使得匹配邊中權(quán)值最大的邊權(quán)值最小算法一：二分最大邊權(quán)，刪除不符合條件的邊，然后進行最大匹配算法二：從權(quán)值最低的邊開始，每次增加一條邊，維護交錯樹森林。最多只可能增加一個交錯軌。因為找到N條交錯軌即可，而維護交錯樹森林的平攤復雜度為O(1)，所以總時間復雜度依然為O(N3)應用舉例：最大最小匹配求一個完備匹配，使得匹配邊中權(quán)值最大的36分析如果有完美匹配，則Alice輸，因為Bob只需沿著匹配邊走即可否則Alice贏：任意求一個最大匹配，Alice把棋子放在任一個未蓋點上，則Bob只能把它移動到已蓋點上（否則得到增廣路）。Alice沿著匹配邊移動，下一步Bob又只能把它移到另一個已蓋點上…只要Bob能移動，Alice就能移動分析如果有完美匹配，則Alice輸，因為Bob只需沿著匹配邊37應用舉例：機器調(diào)度有兩臺機器A和B及N個需要運行的任務。每臺機器有M種不同的模式，而每個任務i都恰好在一臺機器上運行。如果它在機器A上運行，則機器A需要設置為模式ai，如果它在機器B上運行，則機器B需要設置為模式bi。每臺機器上的任務可以按照任意順序執(zhí)行，但是每臺機器每轉(zhuǎn)換一次模式需要重新啟動一次。請合理為每個任務安排一臺機器并合理安排順序，使得機器重啟次數(shù)盡量少應用舉例：機器調(diào)度有兩臺機器A和B及N個需要運行的任務。每臺38機器重啟次數(shù)是兩臺機器需要使用的不同的模式個數(shù)。但是如果把每個任務看成一個X結(jié)點，把每臺機器的每個模式看成一個Y結(jié)點，則此模型沒有任何意義。應該把每個任務看成一條邊，即A機器的每個模式看成一個X結(jié)點，B機器的每個模式看成一個Y結(jié)點，任務i為邊(ai,bi)。本題即為求最少的點讓每條邊都至少和其中的一個點關(guān)聯(lián)，這個數(shù)稱為覆蓋數(shù)(VertexCover)K?nig定理:二分圖覆蓋數(shù)等于匹配數(shù)機器重啟次數(shù)是兩臺機器需要使用的不同的模式個數(shù)。但是如果把每39構(gòu)造最小點覆蓋需要借助匈牙利樹從左邊所有未蓋點出發(fā)擴展匈牙利樹，標記樹中的所有點，則左邊的未標記點和右邊的已標記點組成了最小點覆蓋（黑色）01100101100構(gòu)造最小點覆蓋需要借助匈牙利樹0110010110040為什么恰好選了|M|個點？左邊的未蓋點沒選，因為有標記（作為起點）右邊的未蓋點沒選，因為無標記（如果出現(xiàn)在匈牙利樹中，意味著找到增廣路）在樹中的匹配邊兩邊都有標記不在樹中的匹配邊兩邊都無標記因此匹配邊和標記點一一對應為什么是點覆蓋？有一條邊沒被覆蓋左邊在樹中，而右邊不在樹中，說明匈牙利樹還沒擴展完，矛盾為什么是最優(yōu)的？只考慮最大匹配，顯然至少要M個點才能覆蓋左邊的未標記點和右邊的已標記點為什么恰好選了|M|個點？左邊的未標記點和右邊的已標記點41應用舉例：騎士一個n*n(n<=100)的棋盤上，有一些單位小方格不能放置騎士。棋盤上有若干騎士，任一個騎士不在其他騎士的攻擊范圍內(nèi)。請告訴我棋盤上最多能有幾個騎士。騎士攻擊范圍如圖所示（S是騎士的位置，X表示攻擊范圍）。應用舉例：騎士一個n*n(n<=100)的棋盤上，有一些單位42二分圖最大獨立集如果把剩余單位小方格抽象成圖的頂點，并在相互屬于對方攻擊范圍的頂點對間連線，那么很明顯，由于跳馬特殊的“日”字形路線，使得只有黑色與白色小方格間才有連線，所以此題的模型是一個二分圖G。而我們的目標就是找出G的最大獨立集定理:

若頂點集為V,最大獨立點集為U，最大匹配為M，則|U|=|V|-|M|最大獨立集與最小點覆蓋互補二分圖最大獨立集如果把剩余單位小方格抽象成圖的頂點，并在相互43應用舉例：新漢諾塔有N根柱子，現(xiàn)在有任意正整數(shù)編號的球各一個，請你把盡量多的球放入這N根柱子中，滿足放入球的順序必須是1,2,3,…，且每次只能在某根柱子的最上面放球；同一根柱子中，相鄰兩個球的編號和為完全平方數(shù)。請問，最多能放多少個球在這N根柱子上？例如，4根柱子可以放11個球應用舉例：新漢諾塔有N根柱子，現(xiàn)在有任意正整數(shù)編號的球各一個44最小路徑覆蓋把每個球看做一個頂點，如果兩個球i和j（i<j）的編號和i+j為平方數(shù)，那么把兩個頂點連成一條有向邊i→j。我們首先解決這樣一個判定問題：給定球總數(shù)n和柱子數(shù)m，能否把所有球放到柱子上？即需要解決如下所示的一個問題。最小路徑覆蓋問題.

用盡量少的不相交簡單路徑覆蓋有向無環(huán)圖G的所有頂點。最小路徑覆蓋把每個球看做一個頂點，如果兩個球i和j（i<j）45把所有頂點i拆為兩個：X結(jié)點i和Y結(jié)點i’，如果圖G中存在有向邊i→j，則在二分圖中引入邊i→j’，設二分圖的最大匹配數(shù)為m，則結(jié)果就是n-m。這個結(jié)果不難理解，因為匹配和路徑覆蓋是一一對應的。路徑覆蓋中的每條簡單路徑除了最后一個結(jié)點之外都有惟一的后繼和它對應（即匹配結(jié)點），因此匹配邊數(shù)就是非路徑結(jié)尾的結(jié)點數(shù)。因此匹配數(shù)達到最大時，非路徑結(jié)尾的結(jié)點數(shù)達到最大，故路徑結(jié)尾結(jié)點數(shù)目最少，即路徑數(shù)最少把所有頂點i拆為兩個：X結(jié)點i和Y結(jié)點i’，如果圖G中存在有46二分圖最大權(quán)匹配二分圖最大權(quán)匹配47完全二分圖的最大權(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)48相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)匹配證明：設M*是相等子圖的完美匹配，則根據(jù)定義設M是原圖的任意完美匹配，則關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)49算法思想關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配思想：隨便構(gòu)造一個可行頂標（例如Y結(jié)點頂標為0，X結(jié)點的頂標為它出發(fā)所有弧的最大權(quán)值，然后求相等子圖的最大匹配存在完美匹配，算法終止否則修改頂標使得相等子圖的邊變多，有更大機會存在完美匹配考慮相等子圖不存在完美匹配時的情形算法思想關(guān)鍵：尋找好的可行頂標，使相等子圖有完美匹配50Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為6，不是完美匹配算法在尋找增廣路失敗的同時得到了一棵匈牙利樹雖然此匈牙利樹并沒有包含未蓋點（因此沒有找到增廣路），但仍然含有重要信息Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為51Kuhn-Munkres算法設匈牙利樹中的X結(jié)點集為S，Y結(jié)點集為T，則S到T沒有邊（否則匈牙利樹可以繼續(xù)生長）S到T的邊都是非匹配邊（想一想，為什么）但若把S中所有點的頂標同時減少一個相同整數(shù)a，則S到T中可能會有新邊進入相等子圖SSTTKuhn-Munkres算法設匈牙利樹中的X結(jié)點集為S，Y結(jié)52Kuhn-Munkres算法把S中所有點的頂標同時減少一個相同整數(shù)a，則S到T中可能會有新邊進入相等子圖為了保證S-T的匹配邊不離開相等子圖，把T中所有點的頂標同時增加aSSTT-a+a為保證有新邊進入，取如果S中每個頂標的實際減小值比這個值小則不會有新邊進入；如果比這個值大則頂標將變得不可行Kuhn-Munkres算法把S中所有點的頂標同時減少一個相53Kuhn-Munkres算法設邊(x,y)進入相同子圖y是未蓋點，則找到增廣路y和S中的點z匹配，則把z和y分別加入S和T中每次修改頂標要么找到增廣路，要么使匈牙利樹增加兩個結(jié)點因此一共需要O(n2)次修改頂標操作關(guān)鍵：快速修改頂標SSTT-a+aKuhn-Munkres算法設邊(x,y)進入相同子圖SST54頂標的修改方法1：枚舉S和T中的每個元素，根據(jù)定義計算最小值，每次修改的時間為O(n2)，總O(n4)方法2：對于T中的每個元素y，定義松弛量則a的計算公式變?yōu)轫敇说男薷姆椒?：枚舉S和T中的每個元素，根據(jù)定義計算最小值55頂標的快速修改每次增廣后用O(n2)時間計算所有點的初始slack，由于每次生長匈牙利樹時所有S-T弧的增量相同，因此修改每個slack值只需要常數(shù)時間，計算所有slack值需要O(n)時間每次增廣后最多修改n次頂標，因此每次增廣后修改頂標總時間降為O(n2)，總O(n3)結(jié)論：Kuhn-Munkres算法的總時間復雜度為O(n3)頂標的快速修改每次增廣后用O(n2)時間計算所有點的初始sl56應用舉例：冰激凌加派有n種派和m種冰激凌,把第i種派與第j種冰激凌搭配可以買Wij元錢.給出第k種派的數(shù)量Pk與第k種冰激凌的數(shù)量Ik,求銷售額的最大值和最小值應用舉例：冰激凌加派有n種派和m種冰激凌,把第i種派與第j57最大流問題最大流問題58流網(wǎng)絡定義一個流網(wǎng)絡(flownetwork)G=(V,E)是一個有向圖,每個邊(u,v)有一個非負容量(capacity)c(u,v)>=0.對于不在E中的(u,v),規(guī)定c(u,v)=0有兩個特殊結(jié)點:源(source)s和匯(sink)t.假設對于任意其他點v,存在通路svt流網(wǎng)絡定義一個流網(wǎng)絡(flownetwork)G=(V,59流的定義流(flow)是一個邊的函數(shù)f(u,v),滿足:容量限制:f(u,v)<=c(u,v)對稱性:f(u,v)=-f(u,v)收支平衡:對于不是s或t的其他點u,有把整個網(wǎng)絡的流量定義為(即從s流出的流量):最大流問題:尋找流函數(shù)f,使得網(wǎng)絡流最大流的定義流(flow)是一個邊的函數(shù)f(u,v),滿足:60等價條件1)f是最大流2)殘量網(wǎng)絡中無可增廣路3)存在某個切割(S,T),|f|=c(S,T)12:反證.若存在,可沿它增廣得到更大流23:此時不存在s-t通路.定義S為s可達結(jié)點集,T為可達t結(jié)點集,則|f|=c(S,T)(若跨越(S,T)的弧不滿載,殘量網(wǎng)絡中會有更多弧存在)31:因為對于任意一個切割,f(S,T)=|f|,因此任意可行流量不會超過最小切割的容量等價條件1)f是最大流61Gomory-Hu樹Gomory-Hu樹62每對結(jié)點之間的s-t割有N個點M條邊的無向帶權(quán)圖，對于所有s,t(s<t)，求出s-t的最小割的容量每對結(jié)點之間的s-t割有N個點M條邊的無向帶權(quán)圖，對于所有s63Gomory-Hu樹的構(gòu)造初始時令所有點在同一集合中若所有點屬于不同點集，則退出，否則任找兩個點s,t，同時屬于某點集P求最小s-t割(S,T)，并把P分裂為兩個，一個是在S中的，另一個是在T中的。增加兩點a,a’,增加邊(a,a’),容量為割(S,T)容量，對所有跨越(S,T)的邊(u,v),從圖中刪去,并增設邊(u,a),(a’,v),,容量與邊(u,v)容量相同。轉(zhuǎn)到1Gomory-Hu樹的構(gòu)造初始時令所有點在同一集合中64每次調(diào)用最大流過程都使某點集分裂成兩個非空集合。因此N-1次調(diào)用后算法停止,這時我們共增設了N-1個點對，每個點對中的邊刪去后都會使點集被分成不聯(lián)通的兩部分,也就是說這時點集與增設的N-1個點對中的邊可以構(gòu)成一棵樹。這棵樹就是Gomory-Hu樹，原圖中任兩點的最小割就是其在Gomory-HuTrees中對應點的唯一路徑上的最小邊權(quán)。每次調(diào)用最大流過程都使某點集分裂成兩個非空集合。因此N-1次650,50,20,50,266最后結(jié)果最后結(jié)果67全局最小割全局最小割68全局最小割可以枚舉所有(s,t)點對,求s-t最大流,求最小的一個,但時間…先求Gomory-Hu樹，時間復雜度倒是不錯，但編程比較麻煩…MechthildStoer,FrankWagner,ASimpleMin-CutAlgorithm,1997時間:O(VE+V2logV)全局最小割可以枚舉所有(s,t)點對,求s-t最大流,求69定理對于G的任意兩個結(jié)點s和t,令G/{s,t}表示合并s和t之后的圖,則G的全局最小割可以取G的s-t最小割和G/{s,t}的最小割之間的較小者遞歸計算，則只需要求|V|次s-t最小割可是還是要求|V|次s-t最大流啊?不必,因為可以任意選擇s-t,我們當然是選擇一些比較好算的s-t割了!方法:MAS(MaximumAdjacencySearch)定理對于G的任意兩個結(jié)點s和t,令G/{s,t}表示合并s70MAS從任意結(jié)點a開始生長集合A,每次選擇連接A最緊的結(jié)點(即與A中結(jié)點的所有邊權(quán)和W(A,z)最大的z)加入.本次最后加入的點和其他點形成的割稱為cut-of-the-phase,每次合并最后兩個加入的點.每階段的a可以不變也可以重選MAS從任意結(jié)點a開始生長集合A,每次選擇連接A最緊的結(jié)點71正確性定理:每階段的cut-of-the-phase是最后加入的兩個點的最小s-t割證明:考慮任意s-t割C.對于不是a的其他點v,設v和它前一個加入的點在C中的不同部分,稱v是active的,設Av為v之前(不含)被加入的所有點的集合,Cv是到v為止所有被加入點在C中誘導出的割,只需證明對任意active點v正確性定理:每階段的cut-of-the-phase是最后72證明對active結(jié)點的個數(shù)歸納.第一個active點出現(xiàn)時,誘導出的割只含一條弧,不等式變?yōu)榈仁?滿足;下面考慮在u是v的下一個active結(jié)點,則vu根據(jù)v的選擇方式,W(Av,u)<=W(Av,v),根據(jù)歸納假設,W(Av,v)<=W(Cv)根據(jù)傳遞性,W(Au,u)<=W(Cv)+W(Au\Av,u)由圖上可知,這兩部分是W(Cu)的子集,故W(Av,u)<=W(Cu)完成歸納假設.注意到t總是active的…證明對active結(jié)點的個數(shù)歸納.第一個active點出現(xiàn)73時間復雜度顯然每個phase時間相同,一共|V|次每個phase,每個不在A中的結(jié)點按”與A的邊權(quán)和”為關(guān)鍵字組成優(yōu)先隊列|V|次ExtractMax:取出最緊的點加入A|E|次IncreaseKey:每次選擇結(jié)點u加入后,所有邊uv對應的v(在A外)的關(guān)鍵字要增加w(u,v)二叉堆:O(ElogV)時間復雜度顯然每個phase時間相同,一共|V|次74最大流算法——最短增廣路最大流算法——最短增廣路75概述每次找邊數(shù)最少的增廣路進行增廣定理：最多增廣O(nm)次Edmonds-Karp：每次BFS找增廣路，無需維護附加信息Dinic：多次BFS構(gòu)造層次圖，DFS找增廣路。附加信息：層次（起點到u的距離值）ISAP：動態(tài)維護距離標號（重標號），DFS找增廣路。距離標號是u到匯點的距離下限。選擇：熟練編寫Dinic和ISAP之一即可概述每次找邊數(shù)最少的增廣路進行增廣76嚴格來說，SAP是一類算法的集合，Edmonds-Karp、Dinic和ISAP都屬于它。網(wǎng)絡文章中的SAP基本都是特指ISAP。Dinic一般采用多路增廣，同時用手工模擬棧，而不是遞歸找增廣路當效率要求不高時每次只找一條路，迭代即可ISAP初始距離標號可以統(tǒng)一設為0，也可以用BFS找，效率相差不大一定要用GAP優(yōu)化建議用當前弧優(yōu)化，迭代實現(xiàn)嚴格來說，SAP是一類算法的集合，Edmonds-Karp、77ISAP距離標號d(i)是頂點到非負整數(shù)的映射,它的動機是:描述i到t的最短路下界,它必須滿足以下條件:d(t)=0d(i)<=d(j)+1,對于所有殘量網(wǎng)絡中的邊(i,j)如果d(s)>=n,則殘量網(wǎng)絡中一定沒有s-t路d(i)=d(j)+1的弧(i,j)稱為允許弧,允許路是最短路,強制走允許路ISAP距離標號d(i)是頂點到非負整數(shù)的映射,它的動機是78可以證明,如果一條弧是非允許弧,則只要d(i)不變,它不可能再次變成允許弧因此如果掃描到最后一條弧還是沒有找到允許弧,必須對i進行重新標號:取d(i)=min{d(j)+1|(i,j)在Gf中}并設當前弧為第一條弧,重新標號以后往回走一步而不要繼續(xù)找允許弧,因為當前路徑已經(jīng)不是允許路了（GAP優(yōu)化）假設重標號是把x改成了y，檢查是否還有結(jié)點的距離標號為x，沒有的話終止算法可以證明,如果一條弧是非允許弧,則只要d(i)不變,它79最大流算法——預流推進最大流算法——預流推進80預流推進算法并不檢查整個網(wǎng)絡,而是每次考慮一個結(jié)點,在殘量網(wǎng)絡中只檢查它的鄰居預流推進算法并不始終保持流量平衡條件,而是生成預流。預流也滿足對稱性和容量限制，和流不同的是：流進每個非s點的凈流非負(蓄勢待發(fā),等著流出)。記e(u)為點u的盈余自上而下的水流，邊是管道，點是連接口每個點有一個小型蓄水池用于儲存盈余水量隨著算法進行，每個點的高度逐漸增大水往低處流，直到?jīng)]有水了或者弧滿載(push)；如果有水卻流不動,需要抬高水位,讓它可以繼續(xù)往低處流(relabel)預流推進算法并不檢查整個網(wǎng)絡,而是每次考慮一個結(jié)點,在殘81水源高度固定為|V|,匯的高度固定為0,其他點的高度初始為0,隨著時間推移慢慢增加首先盡量多的從水源把水”推”出來,即讓s出發(fā)的所有弧滿載.水流入某個結(jié)點u后,進入該結(jié)點的蓄水池如果u出發(fā)有到達更低點v的非飽和弧,把盡量多的水推入v(push過程)如果u出發(fā)的所有非飽和弧都連接著與u水平甚至更高的點,把u抬高直到可以推(relabel過程)最終,所有能流到t的水都已經(jīng)流到t了,把所有點的蓄水池里的水都倒回s(只需把水位抬得比s還高)水源高度固定為|V|,匯的高度固定為0,其他點的高度初始82Push操作基本操作PUSH(u,v)的條件u有盈余（e[u]>0），且(u,v)在殘量網(wǎng)絡中，且h(u)=h(v)+1推進量:min{e[u],residual(u,v)}飽和推進(水太多)非飽和推進(水不夠)Push的效果是修改e（盈余）和f（流量）進行非飽和推進后,盈余e[u]變?yōu)?高度函數(shù)，類似于距離標號初始h(s)=|V|,其他h(u)=0Push操作基本操作PUSH(u,v)的條件高度函數(shù)，類似于83Relabel操作基本操作RELABEL(u)的條件u有盈余的殘量網(wǎng)絡中的所有弧(u,v)滿足h[u]<=h[v]即:雖然u有盈余,可是由于位置太低,無法進行PUSH操作,需要RELABEL注意:s和t是不會有盈余的,因此不需要RELABEL既然u有盈余,在殘量網(wǎng)絡中,u出發(fā)一定有弧操作：增加h[u]h[u]=1+min{h[v]|(u,v)在殘量網(wǎng)絡)}Relabel操作基本操作RELABEL(u)的條件84RELABEL-TO-FRONT算法隊列：維護結(jié)點列表,從頭開始掃描,每次對一個盈余結(jié)點進行discharge(即連續(xù)進行push和relabel,直到它沒有盈余)，relabel時放到列表尾部當前弧優(yōu)化：假設v為當前弧，V為空,則需要RELABEL(u)V非空且(u,v)是允許弧,則PUSH(u,v)V非空且(u,v)不是允許弧,無操作RELABEL之后加入GAP優(yōu)化非飽和推進減少，時間復雜度為O(V3)RELABEL-TO-FRONT算法隊列：維護結(jié)點列表,從85最小費用流問題最小費用流問題86最小費用流如下圖,弧上除了網(wǎng)絡外還有一個費用值總費用等于每條弧的流量與費用的乘積最小費用流如下圖,弧上除了網(wǎng)絡外還有一個費用值87殘量網(wǎng)絡殘量網(wǎng)絡N’=(G’,c’,s,t)c’的定義同不帶費用的網(wǎng)絡流問題費用定義正向弧費用為w(e)反向弧費用為-w(e)殘量網(wǎng)絡殘量網(wǎng)絡N’=(G’,c’,s,t)88消圈定理消圈定理:流量為f的可行流x為流量為f的最小費用流當且僅當x沒有負費用增廣圈必要性顯然，用反證法證明充分性。假設存在不同的可行流x0使得它的費用比x更低，則它們的差x1=x0-x是網(wǎng)絡中的負費用循環(huán)流。既然是循環(huán)流，x1一定可以分解為至多m個非零圈流之和，則它們中至少有一個圈是負費用的（有限個非負費用之和仍是非負的），這個圈就是題目中非負增廣圈，矛盾消圈定理消圈定理:流量為f的可行流x為流量為f的最小費用流89消圈算法經(jīng)典的消圈算法(Klein):利用bellman-ford找負圈,最壞情況需要迭代O(C)次每次用O(nm)時間找平均費用最小的增廣圈進行增廣,則對于整數(shù)權(quán)來說最多迭代O(nmlog(nC)),而對于任意實數(shù)權(quán)來說最多迭代O(nm2logn)次結(jié)論:雖然是強多項式時間復雜度,但階太高,不實用消圈算法經(jīng)典的消圈算法(Klein):利用bellman-90連續(xù)最短路算法由Jewell(1958),Iri(1960),Busacker和Gowen(1961)等人獨立提出算法是迭代式的,流量為v時的當前費用流是流量為v的最小費用流最小費用增廣路是殘量網(wǎng)絡中最短的s-t路.由于殘量網(wǎng)絡中的費用有正有負,所以最短路只能用bellman-ford算法計算,每次需要O(mn)時間,假設增廣k次,則時間復雜度為O(kn3),對稀疏圖為O(knm)連續(xù)最短路算法由Jewell(1958),Iri(196091正確性證明如下圖,箭頭都代表多步到達,w是負圈,故P(i->a->b->c->j)+P(j->i)<0,因此P(i->a->b->c->j)<P(i->j)sijtabcPW正確性證明如下圖,箭頭都代表多步到達,w是負圈,故si92假設增廣前s到u的距離為d(u),增廣后的費用函數(shù)為w(e),對于弧e=uv定義一個新的權(quán)值w*(e)=w(e)+d(u)–d(v),則對于任意s-t路X,有w*(X)=w(X)–d(x),即對于權(quán)函數(shù)w(e),w*(e),從s出發(fā)的單源最短路樹完全一樣改進算法:用w*(e)=w(e)+d(u)-d(v)作為權(quán)函數(shù)計算單源最短路d*(x),然后計算出真正的新最短路注意到w*(e)是非負的,所以可以用dijkstra實現(xiàn).為什么是非負的?因為如果w*(e)=w(e)+d(u)-d(v)<0,有d(v)>d(u)+w(e)和d(u)是最短距離矛盾時間復雜度降為O(kn2),稀疏圖O(kmlogn)假設增廣前s到u的距離為d(u),增廣后的費用函數(shù)為w(e93應用：特殊二分圖最佳匹配每個X點有一個權(quán)值，最后要求所有被匹配到的X點的權(quán)和盡量大算法：將X點按照權(quán)值從大到小排序，套用二分圖最大基數(shù)匹配框架，先從權(quán)值大的點開始增廣，得到的就是最優(yōu)解想一想，為什么應用：特殊二分圖最佳匹配每個X點有一個權(quán)值，最后要求所有被匹94最小樹型圖最小樹型圖95朱-劉算法（固定根）首先消除自環(huán)，顯然自環(huán)不在最小樹形圖中。然后判定是否存在最小樹形圖，以根為起點DFS一遍即可。對于除根外的每個頂點，選擇一條權(quán)最小的入邊。如果選出來的V-1條邊不構(gòu)成環(huán)，則可以證明這些邊就是滿足要求的答案。否則收縮每個環(huán)，調(diào)整權(quán)值后求新圖的最小樹形圖朱-劉算法（固定根）首先消除自環(huán)，顯然自環(huán)不在最小樹形圖中。96453-4-3-5從新結(jié)點出去的邊權(quán)不變?nèi)绻昧藦耐饷孢M來的邊，就得刪除里面的邊最終答案加上人工點的權(quán)和453-4-3-5從新結(jié)點出去的邊權(quán)不變97應用：舉辦比賽給出一些有向邊，邊有帶寬，還有一個修建費用，然后開始的時候你有cost錢問你怎么修建一個從0到達其他所有點的網(wǎng)絡，使得所有網(wǎng)絡中最小的帶寬值最大應用：舉辦比賽給出一些有向邊，邊有帶寬，還有一個修建費用，然98題目分析與討論題目分析與討論991.太空旅行太空里有n個星球，你的任務是用最少的步數(shù)從星球S到達星球T。每次可以從一個星球跳到另一個星球，但并不是所有n(n-1)種跳法都是可行的。所有頂點一共有k個“禁止區(qū)間”，其中每個禁止區(qū)間用(U,V1,V2)表示，即從星球U出發(fā)，不可以直接跳到V1,V1+1,V1+2,…,V2這些星球。1.太空旅行太空里有n個星球，你的任務是用最少的步數(shù)從星球S1002.有向圖D和E給一個n個結(jié)點的有向圖D，你可以構(gòu)造這樣一個圖E：D的每條邊對應E的一個結(jié)點（比如，若D有一條邊uv，則E有個結(jié)點的名字叫uv），對于D的兩條邊uv和vw，E中的兩個結(jié)點uv和vw之間連一條有向邊。E中不包含其他邊。給定圖E，你的任務是判斷是否存在對應的圖D。2.有向圖D和E給一個n個結(jié)點的有向圖D，你可以構(gòu)造這樣一個1013.01串處理機給M個長度為N的串，包含字符0,1或星號*。每個串最多包含一個星號。比如01*表示010和011。用盡量少的指令處理所有串，其中每個指令也是一個長度為N，包含0,1或星號，且最多包含一個星號的串（指令10*處理100和101）。例如：{*01,100,011}至少需要兩條指令10*和0*1。N<=10,M<=1000。3.01串處理機給M個長度為N的串，包含字符0,1或星號*。1024.帶寬難題給一個無向圖G，令T(u,v)為u到v的最大流流量。給定矩陣T，求滿足條件的邊數(shù)最少的無向圖G。T(u,u)總是0，T(u,v)總是等于T(v,u)，且T(u,v)<=10000。4.帶寬難題給一個無向圖G，令T(u,v)為u到v的最大流流1035.我是SAM給出一個RxC大小的網(wǎng)格，網(wǎng)格上面放了一些敵軍目標，你可以在網(wǎng)格外發(fā)射子彈，只能沿著垂直或者水平方向發(fā)射，并且會打掉子彈路徑上的所有敵軍目標?，F(xiàn)在需要，計算出最少需要多少子彈，從哪些位置發(fā)射，才能把所有的目標全部打掉。5.我是SAM給出一個RxC大小的網(wǎng)格，網(wǎng)格上面放了一些敵軍1046.爪分解給一個簡單無向圖，每個點的度數(shù)均為3。你的任務是判斷能否把它分解成若干個爪（即K1,3，如下圖）。每條邊應恰好屬于一個爪，同一個結(jié)點可以出現(xiàn)在多個爪里。6.爪分解給一個簡單無向圖，每個點的度數(shù)均為3。你的任務是判1057.螞蟻給n個白點和n個黑點的坐標，要求用n條不相交的線段把它們連接起來，其中每條線段恰好連接一個白點和一個黑點，每個點恰好連接到一條線段。7.螞蟻給n個白點和n個黑點的坐標，要求用n條不相交的線段把1068.鴿子和炸彈給定一個n個點的連通的無向圖，一個點的“鴿子值”定義為將它從圖中刪去后連通塊的個數(shù)。求每個點的“鴿子值”。8.鴿子和炸彈給定一個n個點的連通的無向圖，一個點的“鴿子值1079.少林決勝給一個NxN矩陣，每個格子里都有一個正整數(shù)w(i,j)。你的任務是給每行確定一個整數(shù)row(i)，每列也確定一個整數(shù)col(i)，使得對于任意格子(i,j)，w(i,j)<=row(i)+col(j)。所有row(i)和col(i)之和應盡量小。9.少林決勝給一個NxN矩陣，每個格子里都有一個正整數(shù)w10810.出租車你在一座城市里負責一個大型活動的接待工作。明天將有m位客人從城市的不同位置出發(fā)，到達他們各自的目的地，而且每人的出發(fā)時間已經(jīng)提前給出。你的任務是用盡量少的出租車送他們，使得每次出租車接客人時，至少提前一分鐘到達他所在的位置。注意，為了滿足這一條件，要么這位客人是這輛出租車接送的第一個人，要么在接送完上一個客人后，有足夠的時間從上一個目的地開到這里。為了簡單起見，假定城區(qū)是網(wǎng)格型的，地址用坐標(x,y)表示。出租車從(x1,y1)到(x2,y2)需要行駛|x1-x2|+|y1-y2|分鐘。10.出租車你在一座城市里負責一個大型活動的接待工作。明天將109分析本題的模型是最小路徑覆蓋。在本題中，“時間”是一個天然的序，因此可以構(gòu)圖如下：每個客人是一個結(jié)點，如果同一個出租車可以在接完客人u以后立即接客人v，連邊uv。這樣，我們得到了一個DAG。分析本題的模型是最小路徑覆蓋。在本題中，“時間”是一個天然的11011.公平的收費一個有向無環(huán)圖，邊有權(quán)（全為正），給定起點S終點T，所有點都在S到T的有向路徑上。問能否選出一部分邊，恰當?shù)脑黾铀鼈兊臋?quán)，使得從起點到終點的所有路的權(quán)值和相同，且從起點到終點的每一條路中，最多只有一條邊的權(quán)被修改。若能，問相同的權(quán)值和的最小可能值。11.公平的收費一個有向無環(huán)圖，邊有權(quán)（全為正），給定起點S11112.道路修建某國交通事故發(fā)生的頻率很高，于是國王準備把所有的雙向道路改為單向道路，以便減少事故。為了保持起碼的交通方便，道路改造后任意兩個城市都應相互可達。但遺憾的是，這并不總是能做到的。因此，國王允許新建一些單向道路，以達到任意兩個城市相互可達的目的。由于道路修建的成本較高，新修的道路數(shù)目應盡量小。注意，原有的道路中，兩個城市間不會有兩條或者兩條以上的道路相連，然而在新建的時候，可以在兩個已經(jīng)有道路存在的城市之間建造一條新路。12.道路修建某國交通事故發(fā)生的頻率很高，于是國王準備把所有11213.構(gòu)造二分圖如何構(gòu)造一個恰好有n個完美匹配的二分圖？結(jié)點數(shù)k不超過200，邊數(shù)不限。n<=10613.構(gòu)造二分圖如何構(gòu)造一個恰好有n個完美匹配的二分圖？結(jié)點113圖論劉汝佳課件11414.雙人游戲在一個無向圖上玩雙人游戲，Alice先走，Bob后走。第一次可以任選一個點放一枚棋子，以后每次把棋子移動到一個相鄰點上，并把棋子原先所在的點刪除，誰不能移動就輸。若雙方都采取最優(yōu)策略,誰將取勝?14.雙人游戲在一個無向圖上玩雙人游戲，Alice先走，B11515.兩排有2n個整數(shù)排成兩排，每排n個數(shù)。每次可以交換相同列的兩個數(shù)。要求用最少的交換次數(shù)使得每排的各個數(shù)都不相同。保證有解。n<=50000。下圖描述的是一種可行方案。15.兩排有2n個整數(shù)排成兩排，每排n個數(shù)。每次可以交換相同11616.有向PS圖判斷一個有向圖是否為PS-graph.即可以從一條邊經(jīng)過若干次double和split操作得到。邊數(shù)不超過3500016.有向PS圖判斷一個有向圖是否為PS-graph.即可117目錄DFS相關(guān)算法二分圖相關(guān)算法網(wǎng)絡流相關(guān)算法最小樹形圖目錄DFS相關(guān)算法118DFS相關(guān)算法DFS相關(guān)算法119基本應用找連通分量二分圖判定無向圖的連通性有向圖的連通性基本應用找連通分量120時間戳和邊分類時間初始化為0，最大值為2|E|。數(shù)值本身無意義，但大小關(guān)系有意義voidPREVISIT(intu){pre[u]=++dfs_clock;}voidPOSTVISIT(intu){post[u]=++dfs_clock;}無向圖：只有樹邊和反向邊時間戳和邊分類時間初始化為0，最大值為2|E|。數(shù)值本身無意121無向連通圖的割頂DFS森林一定只有一棵樹。樹根是不是割頂呢？不難發(fā)現(xiàn)，當且僅當它有兩個或更多的兒子時，它才是割頂——無向圖只有樹邊和反向邊，不存在跨越兩棵子樹的邊。對于其他點，情況就要復雜一些。我們有下面的定理：定理：在無向連通圖G的DFS樹中，非根結(jié)點u是G的割頂當且僅當u存在一個兒子w，使得w及其所有后代都沒有反向邊連回u的祖先（連回u不算）。無向連通圖的割頂DFS森林一定只有一棵樹。樹根是不是割頂呢？122定理的證明u存在一個兒子w，使得w及其所有后代都沒有反向邊連回u的祖先（連回u不算）。定理的證明u存在一個兒子w，使得w及其所有后代都沒有反向邊連123為了方便起見，我們設low(u)為u及其后代所能連回的最早的祖先的pre值，則定理中的條件就可以簡寫成：結(jié)點u存在一個兒子w，使得low(w)>=pre(u)。若low(w)>pre(u)，即w最多只能連回自己，則只需刪除(u,w)一條邊就可以讓圖G非連通了。滿足這個條件的邊稱為橋（bridge）為了方便起見，我們設low(u)為u及其后代所能連回的最早的124low函數(shù)本身的計算voiddfs(intu,intfa){//u的父親結(jié)點是fa，初次調(diào)用fa=-1low[u]=pre[u]=++dfs_clock;//初始化low(u)intd=G[u].size();for(inti=0;i<d;i++){//枚舉每條邊(u,w)intw=G[u][i];if(!pre[w]){//沒有訪問過點v（所有pre值初始化為0）dfs(w,u);//w的父親結(jié)點是ulow[u]=min(low[u],low[w]);//用后代的low函數(shù)更新}elseif(w!=fa)low[u]=min(low[u],pre[w]);//用反向邊更新}}low函數(shù)本身的計算voiddfs(intu,int125雙連通與邊-雙連通如果一個無向連通圖沒有割頂，稱它是點-雙連通的，一般簡稱雙連通（biconnected）；如果沒有橋，稱它是邊-雙連通（edge-biconnected）的。點-雙連通的等價條件：任意兩點存在兩條“點不重復”的路徑。這個要求等價于任意兩條邊都在同一個簡單環(huán)中，因此內(nèi)部無割頂。邊-雙連通的等價條件：任意兩點存在兩條“邊不重復”的路徑。這個要求要低一點，只需要每條邊都至少在一個簡單環(huán)中，因此所有邊都不是橋。雙連通與邊-雙連通如果一個無向連通圖沒有割頂，稱它是點-雙連126點/邊-雙連通分量下圖有兩個點-雙連通分量：{1,2,3}和{3,4,5}，但只有一個邊-雙連通分量：{1,2,3,4,5}。點/邊-雙連通分量下圖有兩個點-雙連通分量：{1,2,3}和127算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次dfs染色。因為邊-雙連通分量是沒有公共頂點的，所以只要在第二次dfs的時候保證不經(jīng)過橋即可。點-雙連通分量：Tarjan算法（見后）算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次dfs128voiddfs(intu,intfa){low[u]=pre[u]=++dfs_clock;intd=G[u].size();for(inti=0;i<d;i++){intw=G[u][i];

//求BCC用.每遇到一條邊(u,w)都要加到棧中，不管w是否已編號if(ins[u][w])continue;ins[u][w]=ins[w][u]=1;S.push(mp(u,w));

if(!pre[w]){dfs(w,u);low[u]=min(low[u],low[w]);if(low[w]>=pre[u]){//u是割頂或者根，意味著一個bcc的終止++bcc_cnt;printf("BCC%d,containing(%d,%d):\n",bcc_cnt,u,w);pair<int,int>e;do{e=S.top();S.pop();printf("%d%d\n",e.first,e.second);}while(e!=mp(u,w));}}elseif(w!=fa)low[u]=min(low[u],pre[w]);}}voiddfs(intu,intfa){129有向圖的強連通分量理想情況：依次從I,C,D…出發(fā)DFS，則每次DFS恰好得到一個SCC有向圖的強連通分量理想情況：依次從I,C,D…出發(fā)DFS130Kosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)于各個SCC拓撲順序的有關(guān)信息，而第二次DFS按照這個拓撲順序的逆序進行DFS，從而把每個SCC分開。第一步：對G進行普通的DFS，把各個結(jié)點按照訪問結(jié)束時間從后往前的順序放入列表list中。第二步：計算G的轉(zhuǎn)置GT（即把所有有向邊(u,v)變?yōu)橛邢蜻?v,u)）第三步：對GT進行DFS，其中主循環(huán)中按下標從小到大的順序依次考慮list中的各個結(jié)點，則每次dfs將會得到一個不同的SCC。Kosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)131圓桌騎士每次圓桌會議由至少3個騎士參加，騎士的數(shù)目必須為奇數(shù)，且在圓桌旁坐下后相鄰騎士不能相互憎恨。統(tǒng)計有多少個騎士不可能參加任何一個會議。有n個騎士，m個相互憎恨的騎士對N<=1000,m<=1000000圓桌騎士每次圓桌會議由至少3個騎士參加，騎士的數(shù)目必須為奇數(shù)132以騎士作為頂點建立無向圖G。如果兩個騎士不相互憎恨，在他們之間連一條無向邊。則題目轉(zhuǎn)化為求不在任何一個奇圈上的頂點個數(shù)。如果圖G不連通，應對每個連通分量分別求解。下面假設圖G連通。假設結(jié)點v在某個奇圈上，則根據(jù)定義，該圈上的所有結(jié)點都屬于同一個點-雙連通分量。由于該雙連通分量中含有奇圈，它一定不是二分圖。反過來是否成立呢？即：如果結(jié)點v所屬的某一個雙連通分量B（因為v可能屬于多個雙連通分量）不是二分圖，v是否一定屬于一個奇圈呢？以騎士作為頂點建立無向圖G。如果兩個騎士不相互憎恨，在他們之133問題在于：盡管B不是二分圖意味著它一定包含一個奇圈C，這個C可能并不包含v。我們得想辦法讓v攙和進來。如圖，根據(jù)連通性，從v一定可以到達C中的某個結(jié)點u1；根據(jù)雙連通性，C中還應存在另一個結(jié)點u2，使得從v出發(fā)有兩條不相交路徑（除起點外無公共結(jié)點），分別到u1和u2。由于在C中，從u1到u2的兩條路的長度一奇一偶，總能構(gòu)造出一條經(jīng)過v的奇圈。主算法：對于每個連通分量的每個雙連通分量B，若它不是二分圖，給B中所有結(jié)點標記為“在奇圈上”。問題在于：盡管B不是二分圖意味著它一定包含一個奇圈C，這個C134井下礦工有一座地下的稀有金屬礦由n條隧道和一些連接點組成，其中每條隧道連接兩個連接點。任意兩個連接點之間最多只有一條隧道。為了降低礦工的危險，你的任務是在一些連接點處安裝太平井和相應的逃生裝置，使得不管哪個連接點倒塌，不在此連接點的所有礦工都能到達太平井逃生（假定除倒塌的連接點不能通行外，其他隧道和連接點完好無損）。為了節(jié)約成本，你應當在盡量少的連接點安裝太平井。你還需要計算出在太平井的數(shù)目最小時的安裝方案總數(shù)。井下礦工有一座地下的稀有金屬礦由n條隧道和一些連接點組成，其135本題的模型是：把一個無向圖上選擇盡量少的點涂黑（對應太平井），使得任意刪除一個點后，每個連通分量至少有一個黑點。不難發(fā)現(xiàn)，把割頂涂黑是不劃算的，而且在同一個點-雙連通分量中圖兩個黑點也是不劃算的。進一步分析發(fā)現(xiàn)：如果把每個點-雙連通分量收縮成一個點，則整個圖會變成一棵樹。最優(yōu)方案是在樹的每個葉結(jié)點中選一個非割頂涂黑，兩個問題同時解決。一個特殊情況是整個圖沒有割頂。此時至少需要涂兩個點，方案總數(shù)是C(V,2)，其中V是連接點個數(shù)。本題的模型是：把一個無向圖上選擇盡量少的點涂黑（對應太平井）136等價性證明在數(shù)學中，我們常常需要完成若干個命題的等價性證明。比如，有四個命題a,b,c,d，我們證明ab，然后bc，最后cd。注意每次證明都是雙向的，因此一共完成了6次推導。另一種方法是證明ab，然后bc，接著cd，最后da，只需4次?，F(xiàn)在你的任務是證明n個命題全部等價，且你的朋友已經(jīng)為你作出了m次推導（已知每次推導的內(nèi)容），你至少還需要做幾次推導才能完成整個證明？n<=20000,m<=50000等價性證明在數(shù)學中，我們常常需要完成若干個命題的等價性證明。137分析用圖論術(shù)語來說，本題是給出n個結(jié)點m條邊的有向圖，要求填加盡量少的邊，使得新圖強連通。先找出強連通分量，然后把每個強連通分量縮成一個點，得到一個DAG接下來，設有a個結(jié)點（別忘了，這里的每個結(jié)點對應于原圖的一個強連通分量）的入度為0，b個結(jié)點的出度為0，則max{a,b}就是答案。注意特殊情況：當原圖已經(jīng)強連通時，答案是0而不是1。證明留給讀者。分析用圖論術(shù)語來說，本題是給出n個結(jié)點m條邊的有向圖，要求填138無向仙人掌仙人掌被定義為每個點最多在一個簡單（結(jié)點不重復經(jīng)過）回路上的連通無向圖。你的任務是計算一個無向圖的“仙人掌度”，即它有多少個生成子圖（包括自身）也是仙人掌。如果原圖不是仙人掌，輸出0無向仙人掌仙人掌被定義為每個點最多在一個簡單（結(jié)點不重復經(jīng)過139我們采用分析DFS樹的方法來尋求解決問題的方法。首先，對于一個節(jié)點u，如果它在DFS樹上的某個孩子v滿足low(v)<pre(u)，那么(u，parent(u))這條邊就必然在一個環(huán)上；同樣的，如果u能夠通過反向邊訪問到它的某個祖先節(jié)點w，那么(u，parent(u))這條邊就一定在另外一個環(huán)上。我們對于每個節(jié)點u記錄下這兩種情況發(fā)生的次數(shù)c(u)。如果c(u)>1，那么這個圖必然不是仙人掌，直接輸出0。我們采用分析DFS樹的方法來尋求解決問題的方法。首先，對于一140對于一個仙人掌，如果計算它的仙人掌度呢？顯然，對于一條不屬于任何一個環(huán)的邊，它一定是不可以刪去的，而對于一個長度為L的環(huán)，我們則有L+1種選擇（全部保留或者刪去其中的任意一條邊）。根據(jù)乘法原理，答案就是所有環(huán)長度加一后相乘的結(jié)果。因為所有的工作都可以在一次DFS之內(nèi)完成，所有整個算法的時間復雜度為O(m)。具體實現(xiàn)的時候有一點需要注意：為了避免棧溢出，最好不要在遞歸的同時計算答案。一種較好的方法是遞歸時只記錄每個環(huán)的長度，待全部處理完之后再進行高精度計算。對于一個仙人掌，如果計算它的仙人掌度呢？顯然，對于一條不屬于141二分圖最大匹配二分圖最大匹配142二分圖最大匹配二分圖：結(jié)點可以分為兩部分X和Y，每部分內(nèi)部無邊相連匹配：無公共點的邊集合未蓋點：不與任何匹配邊鄰接的點最大匹配：包含邊數(shù)最多的匹配XY二分圖最大匹配二分圖：結(jié)點可以分為兩部分X和Y，每部分內(nèi)部143交替路、增廣路從未蓋點開始經(jīng)過非匹配邊、匹配邊、非匹配邊……序列，最終通過一條非匹配邊到達另一個未蓋點非匹配邊個數(shù)比匹配邊個數(shù)多一如果把匹配邊和非匹配邊互換，匹配仍合法，但基數(shù)加一交替路、增廣路從未蓋點開始經(jīng)過非匹配邊、匹配邊、非匹配邊……144增廣路定理匹配是最大匹配當且僅當不存在增廣路這個定理適用于任意圖011001011010匈牙利樹思考：忽略虛線邊會導致存在增廣路卻找不到嗎？增廣路定理匹配是最大匹配當且僅當不存在增廣路這個定理適用于任145增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的對稱差G’,則G’在M’中的邊應比M’中更多.G’有三種可能的連通分支孤立點.當某邊(u,v)同時屬于兩個匹配,則u和v都是孤立點.交替回路.該回路中屬于M和M’的邊數(shù)相同交替道路.如果不存在增廣路,則|M’|=|M|,與假設矛盾;如果存在M關(guān)于M’的增廣路,又與M’是最大匹配矛盾,因此存在M’關(guān)于M的增廣路增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.146Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在完全匹配(X的結(jié)點全被匹配)的充要條件是對于X的任意子集A,恒有必要性.若存在A使得右邊>左邊,則A無法全部匹配充分性.假設G的最大匹配M不是完全匹配,一定存在結(jié)點X的結(jié)點x0關(guān)于M是非飽和點.如果x0的鄰集為空,則令A={x0}引出矛盾;如果非空則其中每個結(jié)點均為飽和點(否則會有增廣路).尋找與x0為端點的關(guān)于M的一切交錯路,設其中Y結(jié)點的集合為Y’,X結(jié)點的集合為X’,則Y’結(jié)點與X’-{x0}的結(jié)點一一對應,因此|X’|>|Y’|,令A=X’引出矛盾.Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在完全匹配(147二分圖最大匹配算法匈牙利樹是從所有未蓋點,而不是從固定未蓋點長出的樹Edmonds-Karp算法:把所有未蓋點放到隊列中,BFS尋找/增廣路時間均為O(m)最多找O(n)次時間復雜度O(nm)Hopcroft算法：每次沿多條增廣路同時增廣每次尋找若干條結(jié)點不相交最短增廣路每次的最短增廣路集是極大的時間復雜度基于DFS的算法:每次選一個未蓋點u進行DFS.如果找不到增廣路則換一個未蓋點,且以后再也不從u出發(fā)找增廣路.二分圖最大匹配算法匈牙利樹是從所有未蓋點,而不是從固定未蓋148Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要