圖論劉汝佳課件

目錄DFS相關(guān)算法二分圖相關(guān)算法網(wǎng)絡(luò)流相關(guān)算法最小樹(shù)形圖目錄DFS相關(guān)算法1DFS相關(guān)算法DFS相關(guān)算法2基本應(yīng)用找連通分量二分圖判定無(wú)向圖的連通性有向圖的連通性基本應(yīng)用找連通分量3時(shí)間戳和邊分類時(shí)間初始化為0，最大值為2|E|。數(shù)值本身無(wú)意義，但大小關(guān)系有意義voidPREVISIT(intu){pre[u]=++dfs_clock;}voidPOSTVISIT(intu){post[u]=++dfs_clock;}無(wú)向圖：只有樹(shù)邊和反向邊時(shí)間戳和邊分類時(shí)間初始化為0，最大值為2|E|。數(shù)值本身無(wú)意4無(wú)向連通圖的割頂DFS森林一定只有一棵樹(shù)。樹(shù)根是不是割頂呢？不難發(fā)現(xiàn)，當(dāng)且僅當(dāng)它有兩個(gè)或更多的兒子時(shí)，它才是割頂——無(wú)向圖只有樹(shù)邊和反向邊，不存在跨越兩棵子樹(shù)的邊。對(duì)于其他點(diǎn)，情況就要復(fù)雜一些。我們有下面的定理：定理：在無(wú)向連通圖G的DFS樹(shù)中，非根結(jié)點(diǎn)u是G的割頂當(dāng)且僅當(dāng)u存在一個(gè)兒子w，使得w及其所有后代都沒(méi)有反向邊連回u的祖先（連回u不算）。無(wú)向連通圖的割頂DFS森林一定只有一棵樹(shù)。樹(shù)根是不是割頂呢？5定理的證明u存在一個(gè)兒子w，使得w及其所有后代都沒(méi)有反向邊連回u的祖先（連回u不算）。定理的證明u存在一個(gè)兒子w，使得w及其所有后代都沒(méi)有反向邊連6為了方便起見(jiàn)，我們?cè)O(shè)low(u)為u及其后代所能連回的最早的祖先的pre值，則定理中的條件就可以簡(jiǎn)寫成：結(jié)點(diǎn)u存在一個(gè)兒子w，使得low(w)>=pre(u)。若low(w)>pre(u)，即w最多只能連回自己，則只需刪除(u,w)一條邊就可以讓圖G非連通了。滿足這個(gè)條件的邊稱為橋（bridge）為了方便起見(jiàn)，我們?cè)O(shè)low(u)為u及其后代所能連回的最早的7low函數(shù)本身的計(jì)算voiddfs(intu,intfa){//u的父親結(jié)點(diǎn)是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]){//沒(méi)有訪問(wèn)過(guò)點(diǎn)v（所有pre值初始化為0）dfs(w,u);//w的父親結(jié)點(diǎn)是ulow[u]=min(low[u],low[w]);//用后代的low函數(shù)更新}elseif(w!=fa)low[u]=min(low[u],pre[w]);//用反向邊更新}}low函數(shù)本身的計(jì)算voiddfs(intu,int8雙連通與邊-雙連通如果一個(gè)無(wú)向連通圖沒(méi)有割頂，稱它是點(diǎn)-雙連通的，一般簡(jiǎn)稱雙連通（biconnected）；如果沒(méi)有橋，稱它是邊-雙連通（edge-biconnected）的。點(diǎn)-雙連通的等價(jià)條件：任意兩點(diǎn)存在兩條“點(diǎn)不重復(fù)”的路徑。這個(gè)要求等價(jià)于任意兩條邊都在同一個(gè)簡(jiǎn)單環(huán)中，因此內(nèi)部無(wú)割頂。邊-雙連通的等價(jià)條件：任意兩點(diǎn)存在兩條“邊不重復(fù)”的路徑。這個(gè)要求要低一點(diǎn)，只需要每條邊都至少在一個(gè)簡(jiǎn)單環(huán)中，因此所有邊都不是橋。雙連通與邊-雙連通如果一個(gè)無(wú)向連通圖沒(méi)有割頂，稱它是點(diǎn)-雙連9點(diǎn)/邊-雙連通分量下圖有兩個(gè)點(diǎn)-雙連通分量：{1,2,3}和{3,4,5}，但只有一個(gè)邊-雙連通分量：{1,2,3,4,5}。點(diǎn)/邊-雙連通分量下圖有兩個(gè)點(diǎn)-雙連通分量：{1,2,3}和10算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次dfs染色。因?yàn)檫?雙連通分量是沒(méi)有公共頂點(diǎn)的，所以只要在第二次dfs的時(shí)候保證不經(jīng)過(guò)橋即可。點(diǎn)-雙連通分量：Tarjan算法（見(jiàn)后）算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次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是否已編號(hào)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是割頂或者根，意味著一個(gè)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有向圖的強(qiáng)連通分量理想情況：依次從I,C,D…出發(fā)DFS，則每次DFS恰好得到一個(gè)SCC有向圖的強(qiáng)連通分量理想情況：依次從I,C,D…出發(fā)DFS13Kosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)于各個(gè)SCC拓?fù)漤樞虻挠嘘P(guān)信息，而第二次DFS按照這個(gè)拓?fù)漤樞虻哪嫘蜻M(jìn)行DFS，從而把每個(gè)SCC分開(kāi)。第一步：對(duì)G進(jìn)行普通的DFS，把各個(gè)結(jié)點(diǎn)按照訪問(wèn)結(jié)束時(shí)間從后往前的順序放入列表list中。第二步：計(jì)算G的轉(zhuǎn)置GT（即把所有有向邊(u,v)變?yōu)橛邢蜻?v,u)）第三步：對(duì)GT進(jìn)行DFS，其中主循環(huán)中按下標(biāo)從小到大的順序依次考慮list中的各個(gè)結(jié)點(diǎn)，則每次dfs將會(huì)得到一個(gè)不同的SCC。Kosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)14圓桌騎士每次圓桌會(huì)議由至少3個(gè)騎士參加，騎士的數(shù)目必須為奇數(shù)，且在圓桌旁坐下后相鄰騎士不能相互憎恨。統(tǒng)計(jì)有多少個(gè)騎士不可能參加任何一個(gè)會(huì)議。有n個(gè)騎士，m個(gè)相互憎恨的騎士對(duì)N<=1000,m<=1000000圓桌騎士每次圓桌會(huì)議由至少3個(gè)騎士參加，騎士的數(shù)目必須為奇數(shù)15以騎士作為頂點(diǎn)建立無(wú)向圖G。如果兩個(gè)騎士不相互憎恨，在他們之間連一條無(wú)向邊。則題目轉(zhuǎn)化為求不在任何一個(gè)奇圈上的頂點(diǎn)個(gè)數(shù)。如果圖G不連通，應(yīng)對(duì)每個(gè)連通分量分別求解。下面假設(shè)圖G連通。假設(shè)結(jié)點(diǎn)v在某個(gè)奇圈上，則根據(jù)定義，該圈上的所有結(jié)點(diǎn)都屬于同一個(gè)點(diǎn)-雙連通分量。由于該雙連通分量中含有奇圈，它一定不是二分圖。反過(guò)來(lái)是否成立呢？即：如果結(jié)點(diǎn)v所屬的某一個(gè)雙連通分量B（因?yàn)関可能屬于多個(gè)雙連通分量）不是二分圖，v是否一定屬于一個(gè)奇圈呢？以騎士作為頂點(diǎn)建立無(wú)向圖G。如果兩個(gè)騎士不相互憎恨，在他們之16問(wèn)題在于：盡管B不是二分圖意味著它一定包含一個(gè)奇圈C，這個(gè)C可能并不包含v。我們得想辦法讓v攙和進(jìn)來(lái)。如圖，根據(jù)連通性，從v一定可以到達(dá)C中的某個(gè)結(jié)點(diǎn)u1；根據(jù)雙連通性，C中還應(yīng)存在另一個(gè)結(jié)點(diǎn)u2，使得從v出發(fā)有兩條不相交路徑（除起點(diǎn)外無(wú)公共結(jié)點(diǎn)），分別到u1和u2。由于在C中，從u1到u2的兩條路的長(zhǎng)度一奇一偶，總能構(gòu)造出一條經(jīng)過(guò)v的奇圈。主算法：對(duì)于每個(gè)連通分量的每個(gè)雙連通分量B，若它不是二分圖，給B中所有結(jié)點(diǎn)標(biāo)記為“在奇圈上”。問(wèn)題在于：盡管B不是二分圖意味著它一定包含一個(gè)奇圈C，這個(gè)C17井下礦工有一座地下的稀有金屬礦由n條隧道和一些連接點(diǎn)組成，其中每條隧道連接兩個(gè)連接點(diǎn)。任意兩個(gè)連接點(diǎn)之間最多只有一條隧道。為了降低礦工的危險(xiǎn)，你的任務(wù)是在一些連接點(diǎn)處安裝太平井和相應(yīng)的逃生裝置，使得不管哪個(gè)連接點(diǎn)倒塌，不在此連接點(diǎn)的所有礦工都能到達(dá)太平井逃生（假定除倒塌的連接點(diǎn)不能通行外，其他隧道和連接點(diǎn)完好無(wú)損）。為了節(jié)約成本，你應(yīng)當(dāng)在盡量少的連接點(diǎn)安裝太平井。你還需要計(jì)算出在太平井的數(shù)目最小時(shí)的安裝方案總數(shù)。井下礦工有一座地下的稀有金屬礦由n條隧道和一些連接點(diǎn)組成，其18本題的模型是：把一個(gè)無(wú)向圖上選擇盡量少的點(diǎn)涂黑（對(duì)應(yīng)太平井），使得任意刪除一個(gè)點(diǎn)后，每個(gè)連通分量至少有一個(gè)黑點(diǎn)。不難發(fā)現(xiàn)，把割頂涂黑是不劃算的，而且在同一個(gè)點(diǎn)-雙連通分量中圖兩個(gè)黑點(diǎn)也是不劃算的。進(jìn)一步分析發(fā)現(xiàn)：如果把每個(gè)點(diǎn)-雙連通分量收縮成一個(gè)點(diǎn)，則整個(gè)圖會(huì)變成一棵樹(shù)。最優(yōu)方案是在樹(shù)的每個(gè)葉結(jié)點(diǎn)中選一個(gè)非割頂涂黑，兩個(gè)問(wèn)題同時(shí)解決。一個(gè)特殊情況是整個(gè)圖沒(méi)有割頂。此時(shí)至少需要涂?jī)蓚€(gè)點(diǎn)，方案總數(shù)是C(V,2)，其中V是連接點(diǎn)個(gè)數(shù)。本題的模型是：把一個(gè)無(wú)向圖上選擇盡量少的點(diǎn)涂黑（對(duì)應(yīng)太平井）19等價(jià)性證明在數(shù)學(xué)中，我們常常需要完成若干個(gè)命題的等價(jià)性證明。比如，有四個(gè)命題a,b,c,d，我們證明a

b，然后b

c，最后c

d。注意每次證明都是雙向的，因此一共完成了6次推導(dǎo)。另一種方法是證明a

b，然后b

c，接著c

d，最后d

a，只需4次。現(xiàn)在你的任務(wù)是證明n個(gè)命題全部等價(jià)，且你的朋友已經(jīng)為你作出了m次推導(dǎo)（已知每次推導(dǎo)的內(nèi)容），你至少還需要做幾次推導(dǎo)才能完成整個(gè)證明？n<=20000,m<=50000等價(jià)性證明在數(shù)學(xué)中，我們常常需要完成若干個(gè)命題的等價(jià)性證明。20分析用圖論術(shù)語(yǔ)來(lái)說(shuō)，本題是給出n個(gè)結(jié)點(diǎn)m條邊的有向圖，要求填加盡量少的邊，使得新圖強(qiáng)連通。先找出強(qiáng)連通分量，然后把每個(gè)強(qiáng)連通分量縮成一個(gè)點(diǎn)，得到一個(gè)DAG接下來(lái)，設(shè)有a個(gè)結(jié)點(diǎn)（別忘了，這里的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于原圖的一個(gè)強(qiáng)連通分量）的入度為0，b個(gè)結(jié)點(diǎn)的出度為0，則max{a,b}就是答案。注意特殊情況：當(dāng)原圖已經(jīng)強(qiáng)連通時(shí)，答案是0而不是1。證明留給讀者。分析用圖論術(shù)語(yǔ)來(lái)說(shuō)，本題是給出n個(gè)結(jié)點(diǎn)m條邊的有向圖，要求填21無(wú)向仙人掌仙人掌被定義為每個(gè)點(diǎn)最多在一個(gè)簡(jiǎn)單（結(jié)點(diǎn)不重復(fù)經(jīng)過(guò)）回路上的連通無(wú)向圖。你的任務(wù)是計(jì)算一個(gè)無(wú)向圖的“仙人掌度”，即它有多少個(gè)生成子圖（包括自身）也是仙人掌。如果原圖不是仙人掌，輸出0無(wú)向仙人掌仙人掌被定義為每個(gè)點(diǎn)最多在一個(gè)簡(jiǎn)單（結(jié)點(diǎn)不重復(fù)經(jīng)過(guò)22我們采用分析DFS樹(shù)的方法來(lái)尋求解決問(wèn)題的方法。首先，對(duì)于一個(gè)節(jié)點(diǎn)u，如果它在DFS樹(shù)上的某個(gè)孩子v滿足low(v)<pre(u)，那么(u，parent(u))這條邊就必然在一個(gè)環(huán)上；同樣的，如果u能夠通過(guò)反向邊訪問(wèn)到它的某個(gè)祖先節(jié)點(diǎn)w，那么(u，parent(u))這條邊就一定在另外一個(gè)環(huán)上。我們對(duì)于每個(gè)節(jié)點(diǎn)u記錄下這兩種情況發(fā)生的次數(shù)c(u)。如果c(u)>1，那么這個(gè)圖必然不是仙人掌，直接輸出0。我們采用分析DFS樹(shù)的方法來(lái)尋求解決問(wèn)題的方法。首先，對(duì)于一23對(duì)于一個(gè)仙人掌，如果計(jì)算它的仙人掌度呢？顯然，對(duì)于一條不屬于任何一個(gè)環(huán)的邊，它一定是不可以刪去的，而對(duì)于一個(gè)長(zhǎng)度為L(zhǎng)的環(huán)，我們則有L+1種選擇（全部保留或者刪去其中的任意一條邊）。根據(jù)乘法原理，答案就是所有環(huán)長(zhǎng)度加一后相乘的結(jié)果。因?yàn)樗械墓ぷ鞫伎梢栽谝淮蜠FS之內(nèi)完成，所有整個(gè)算法的時(shí)間復(fù)雜度為O(m)。具體實(shí)現(xiàn)的時(shí)候有一點(diǎn)需要注意：為了避免棧溢出，最好不要在遞歸的同時(shí)計(jì)算答案。一種較好的方法是遞歸時(shí)只記錄每個(gè)環(huán)的長(zhǎng)度，待全部處理完之后再進(jìn)行高精度計(jì)算。對(duì)于一個(gè)仙人掌，如果計(jì)算它的仙人掌度呢？顯然，對(duì)于一條不屬于24二分圖最大匹配二分圖最大匹配25二分圖最大匹配二分圖：結(jié)點(diǎn)可以分為兩部分X和Y，每部分內(nèi)部無(wú)邊相連匹配：無(wú)公共點(diǎn)的邊集合未蓋點(diǎn)：不與任何匹配邊鄰接的點(diǎn)最大匹配：包含邊數(shù)最多的匹配XY二分圖最大匹配二分圖：結(jié)點(diǎn)可以分為兩部分X和Y，每部分內(nèi)部26交替路、增廣路從未蓋點(diǎn)開(kāi)始經(jīng)過(guò)非匹配邊、匹配邊、非匹配邊……序列，最終通過(guò)一條非匹配邊到達(dá)另一個(gè)未蓋點(diǎn)非匹配邊個(gè)數(shù)比匹配邊個(gè)數(shù)多一如果把匹配邊和非匹配邊互換，匹配仍合法，但基數(shù)加一交替路、增廣路從未蓋點(diǎn)開(kāi)始經(jīng)過(guò)非匹配邊、匹配邊、非匹配邊……27增廣路定理匹配是最大匹配當(dāng)且僅當(dāng)不存在增廣路這個(gè)定理適用于任意圖011001011010匈牙利樹(shù)思考：忽略虛線邊會(huì)導(dǎo)致存在增廣路卻找不到嗎？增廣路定理匹配是最大匹配當(dāng)且僅當(dāng)不存在增廣路這個(gè)定理適用于任28增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的對(duì)稱差G’,則G’在M’中的邊應(yīng)比M’中更多.G’有三種可能的連通分支孤立點(diǎn).當(dāng)某邊(u,v)同時(shí)屬于兩個(gè)匹配,則u和v都是孤立點(diǎn).交替回路.該回路中屬于M和M’的邊數(shù)相同交替道路.如果不存在增廣路,則|M’|=|M|,與假設(shè)矛盾;如果存在M關(guān)于M’的增廣路,又與M’是最大匹配矛盾,因此存在M’關(guān)于M的增廣路增廣路定理的證明必要性.如果存在則增廣后得到更大匹配.29Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在完全匹配(X的結(jié)點(diǎn)全被匹配)的充要條件是對(duì)于X的任意子集A,恒有必要性.若存在A使得右邊>左邊,則A無(wú)法全部匹配充分性.假設(shè)G的最大匹配M不是完全匹配,一定存在結(jié)點(diǎn)X的結(jié)點(diǎn)x0關(guān)于M是非飽和點(diǎn).如果x0的鄰集為空,則令A(yù)={x0}引出矛盾;如果非空則其中每個(gè)結(jié)點(diǎn)均為飽和點(diǎn)(否則會(huì)有增廣路).尋找與x0為端點(diǎn)的關(guān)于M的一切交錯(cuò)路,設(shè)其中Y結(jié)點(diǎn)的集合為Y’,X結(jié)點(diǎn)的集合為X’,則Y’結(jié)點(diǎn)與X’-{x0}的結(jié)點(diǎn)一一對(duì)應(yīng),因此|X’|>|Y’|,令A(yù)=X’引出矛盾.Hall定理在二分圖(X,Y,E)中,X到Y(jié)存在完全匹配(30二分圖最大匹配算法匈牙利樹(shù)是從所有未蓋點(diǎn),而不是從固定未蓋點(diǎn)長(zhǎng)出的樹(shù)Edmonds-Karp算法:把所有未蓋點(diǎn)放到隊(duì)列中,BFS尋找/增廣路時(shí)間均為O(m)最多找O(n)次時(shí)間復(fù)雜度O(nm)Hopcroft算法：每次沿多條增廣路同時(shí)增廣每次尋找若干條結(jié)點(diǎn)不相交最短增廣路每次的最短增廣路集是極大的時(shí)間復(fù)雜度基于DFS的算法:每次選一個(gè)未蓋點(diǎn)u進(jìn)行DFS.如果找不到增廣路則換一個(gè)未蓋點(diǎn),且以后再也不從u出發(fā)找增廣路.二分圖最大匹配算法匈牙利樹(shù)是從所有未蓋點(diǎn),而不是從固定未蓋31Hopcroft算法可以證明：如果每次找到的最短增廣路集是極大的，則只需要增廣次關(guān)鍵：用O(m)時(shí)間找一個(gè)極大最短增廣路集步驟1：用距離標(biāo)號(hào)擴(kuò)展匈牙利樹(shù)，找到第一個(gè)未蓋點(diǎn)時(shí)并不停止，把此時(shí)的距離標(biāo)號(hào)設(shè)為上限。這樣，找到的所有未蓋點(diǎn)距離標(biāo)號(hào)都相同步驟2：每次任取一個(gè)未蓋點(diǎn)，用DFS找到它到起點(diǎn)的增廣路(只沿著距離標(biāo)號(hào)下降的方向),標(biāo)記經(jīng)過(guò)的點(diǎn),找所有增廣路的總時(shí)間為O(m)Hopcroft算法可以證明：如果每次找到的最短增廣路集是極32基于DFS的算法從貪心匹配,而不是空匹配開(kāi)始每次從一個(gè)未蓋點(diǎn)開(kāi)始DFS找增廣路,而不是一次性把所有未蓋點(diǎn)放入隊(duì)列進(jìn)行BFS如果從一個(gè)未蓋點(diǎn)u開(kāi)始找不到增廣路,則以后再也不用考慮u了.為什么?定理:假設(shè)G的匹配為M,不存在從非飽和點(diǎn)u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配的增廣路基于DFS的算法從貪心匹配,而不是空匹配開(kāi)始33定理的證明(1)定理:假設(shè)G的匹配為M,不存在從非飽和點(diǎn)u出發(fā)的增廣路,而存在另外一條增廣路P,則G也不存在從u出發(fā)關(guān)于增廣后新匹配M’的增廣路證明:假設(shè)增廣后從u出發(fā)有增廣路Q.若Q與P不相交,則Q就是M-增廣路,矛盾.因此Q與P相交.下面借助P和Q構(gòu)造出從u出發(fā)關(guān)于M的增廣路,從而得到矛盾定理的證明(1)定理:假設(shè)G的匹配為M,不存在從非飽和點(diǎn)34定理的證明(2)Q與P相交.設(shè)P的兩個(gè)M-非飽和點(diǎn)為u0和v0,而Q的兩個(gè)M’-非飽和點(diǎn)是u,v.從u開(kāi)始沿Q走,設(shè)第一個(gè)P中結(jié)點(diǎn)為w,則w把P分為兩段,其中必有一段以M中邊與w關(guān)聯(lián),得到從u出發(fā)增廣路wv0u0vuPQ定理的證明(2)Q與P相交.設(shè)P的兩個(gè)M-非飽和點(diǎn)為u0和35應(yīng)用舉例：最大最小匹配求一個(gè)完備匹配，使得匹配邊中權(quán)值最大的邊權(quán)值最小算法一：二分最大邊權(quán)，刪除不符合條件的邊，然后進(jìn)行最大匹配算法二：從權(quán)值最低的邊開(kāi)始，每次增加一條邊，維護(hù)交錯(cuò)樹(shù)森林。最多只可能增加一個(gè)交錯(cuò)軌。因?yàn)檎业絅條交錯(cuò)軌即可，而維護(hù)交錯(cuò)樹(shù)森林的平攤復(fù)雜度為O(1)，所以總時(shí)間復(fù)雜度依然為O(N3)應(yīng)用舉例：最大最小匹配求一個(gè)完備匹配，使得匹配邊中權(quán)值最大的36分析如果有完美匹配，則Alice輸，因?yàn)锽ob只需沿著匹配邊走即可否則Alice贏：任意求一個(gè)最大匹配，Alice把棋子放在任一個(gè)未蓋點(diǎn)上，則Bob只能把它移動(dòng)到已蓋點(diǎn)上（否則得到增廣路）。Alice沿著匹配邊移動(dòng)，下一步Bob又只能把它移到另一個(gè)已蓋點(diǎn)上…只要Bob能移動(dòng)，Alice就能移動(dòng)分析如果有完美匹配，則Alice輸，因?yàn)锽ob只需沿著匹配邊37應(yīng)用舉例：機(jī)器調(diào)度有兩臺(tái)機(jī)器A和B及N個(gè)需要運(yùn)行的任務(wù)。每臺(tái)機(jī)器有M種不同的模式，而每個(gè)任務(wù)i都恰好在一臺(tái)機(jī)器上運(yùn)行。如果它在機(jī)器A上運(yùn)行，則機(jī)器A需要設(shè)置為模式ai，如果它在機(jī)器B上運(yùn)行，則機(jī)器B需要設(shè)置為模式bi。每臺(tái)機(jī)器上的任務(wù)可以按照任意順序執(zhí)行，但是每臺(tái)機(jī)器每轉(zhuǎn)換一次模式需要重新啟動(dòng)一次。請(qǐng)合理為每個(gè)任務(wù)安排一臺(tái)機(jī)器并合理安排順序，使得機(jī)器重啟次數(shù)盡量少應(yīng)用舉例：機(jī)器調(diào)度有兩臺(tái)機(jī)器A和B及N個(gè)需要運(yùn)行的任務(wù)。每臺(tái)38機(jī)器重啟次數(shù)是兩臺(tái)機(jī)器需要使用的不同的模式個(gè)數(shù)。但是如果把每個(gè)任務(wù)看成一個(gè)X結(jié)點(diǎn)，把每臺(tái)機(jī)器的每個(gè)模式看成一個(gè)Y結(jié)點(diǎn)，則此模型沒(méi)有任何意義。應(yīng)該把每個(gè)任務(wù)看成一條邊，即A機(jī)器的每個(gè)模式看成一個(gè)X結(jié)點(diǎn)，B機(jī)器的每個(gè)模式看成一個(gè)Y結(jié)點(diǎn)，任務(wù)i為邊(ai,bi)。本題即為求最少的點(diǎn)讓每條邊都至少和其中的一個(gè)點(diǎn)關(guān)聯(lián)，這個(gè)數(shù)稱為覆蓋數(shù)(VertexCover)K?nig定理:二分圖覆蓋數(shù)等于匹配數(shù)機(jī)器重啟次數(shù)是兩臺(tái)機(jī)器需要使用的不同的模式個(gè)數(shù)。但是如果把每39構(gòu)造最小點(diǎn)覆蓋需要借助匈牙利樹(shù)從左邊所有未蓋點(diǎn)出發(fā)擴(kuò)展匈牙利樹(shù)，標(biāo)記樹(shù)中的所有點(diǎn)，則左邊的未標(biāo)記點(diǎn)和右邊的已標(biāo)記點(diǎn)組成了最小點(diǎn)覆蓋（黑色）01100101100構(gòu)造最小點(diǎn)覆蓋需要借助匈牙利樹(shù)0110010110040為什么恰好選了|M|個(gè)點(diǎn)？左邊的未蓋點(diǎn)沒(méi)選，因?yàn)橛袠?biāo)記（作為起點(diǎn)）右邊的未蓋點(diǎn)沒(méi)選，因?yàn)闊o(wú)標(biāo)記（如果出現(xiàn)在匈牙利樹(shù)中，意味著找到增廣路）在樹(shù)中的匹配邊兩邊都有標(biāo)記不在樹(shù)中的匹配邊兩邊都無(wú)標(biāo)記因此匹配邊和標(biāo)記點(diǎn)一一對(duì)應(yīng)為什么是點(diǎn)覆蓋？有一條邊沒(méi)被覆蓋

左邊在樹(shù)中，而右邊不在樹(shù)中，說(shuō)明匈牙利樹(shù)還沒(méi)擴(kuò)展完，矛盾為什么是最優(yōu)的？只考慮最大匹配，顯然至少要M個(gè)點(diǎn)才能覆蓋左邊的未標(biāo)記點(diǎn)和右邊的已標(biāo)記點(diǎn)為什么恰好選了|M|個(gè)點(diǎn)？左邊的未標(biāo)記點(diǎn)和右邊的已標(biāo)記點(diǎn)41應(yīng)用舉例：騎士一個(gè)n*n(n<=100)的棋盤上，有一些單位小方格不能放置騎士。棋盤上有若干騎士，任一個(gè)騎士不在其他騎士的攻擊范圍內(nèi)。請(qǐng)告訴我棋盤上最多能有幾個(gè)騎士。騎士攻擊范圍如圖所示（S是騎士的位置，X表示攻擊范圍）。應(yīng)用舉例：騎士一個(gè)n*n(n<=100)的棋盤上，有一些單位42二分圖最大獨(dú)立集如果把剩余單位小方格抽象成圖的頂點(diǎn)，并在相互屬于對(duì)方攻擊范圍的頂點(diǎn)對(duì)間連線，那么很明顯，由于跳馬特殊的“日”字形路線，使得只有黑色與白色小方格間才有連線，所以此題的模型是一個(gè)二分圖G。而我們的目標(biāo)就是找出G的最大獨(dú)立集定理:

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

用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)圖G的所有頂點(diǎn)。最小路徑覆蓋把每個(gè)球看做一個(gè)頂點(diǎn)，如果兩個(gè)球i和j（i<j）45把所有頂點(diǎn)i拆為兩個(gè)：X結(jié)點(diǎn)i和Y結(jié)點(diǎn)i’，如果圖G中存在有向邊i→j，則在二分圖中引入邊i→j’，設(shè)二分圖的最大匹配數(shù)為m，則結(jié)果就是n-m。這個(gè)結(jié)果不難理解，因?yàn)槠ヅ浜吐窂礁采w是一一對(duì)應(yīng)的。路徑覆蓋中的每條簡(jiǎn)單路徑除了最后一個(gè)結(jié)點(diǎn)之外都有惟一的后繼和它對(duì)應(yīng)（即匹配結(jié)點(diǎn)），因此匹配邊數(shù)就是非路徑結(jié)尾的結(jié)點(diǎn)數(shù)。因此匹配數(shù)達(dá)到最大時(shí)，非路徑結(jié)尾的結(jié)點(diǎn)數(shù)達(dá)到最大，故路徑結(jié)尾結(jié)點(diǎn)數(shù)目最少，即路徑數(shù)最少把所有頂點(diǎn)i拆為兩個(gè)：X結(jié)點(diǎn)i和Y結(jié)點(diǎn)i’，如果圖G中存在有46二分圖最大權(quán)匹配二分圖最大權(quán)匹配47完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個(gè)非負(fù)整數(shù)權(quán)值目標(biāo)：求出權(quán)和最大的完美匹配特點(diǎn)：完美匹配容易求，但權(quán)最大的不易可行頂標(biāo)：結(jié)點(diǎn)函數(shù)l，對(duì)任意弧(x,y)滿足相等子圖：G的生成子圖，包含所有點(diǎn)，但只包含滿足l(x)+l(y)=w(x,y)的所有弧(x,y)完全二分圖的最大權(quán)完美匹配完全二分圖，每條邊有一個(gè)非負(fù)整數(shù)權(quán)48相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)匹配證明：設(shè)M*是相等子圖的完美匹配，則根據(jù)定義設(shè)M是原圖的任意完美匹配，則關(guān)鍵：尋找好的可行頂標(biāo)，使相等子圖有完美匹配相等子圖定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權(quán)49算法思想關(guān)鍵：尋找好的可行頂標(biāo)，使相等子圖有完美匹配思想：隨便構(gòu)造一個(gè)可行頂標(biāo)（例如Y結(jié)點(diǎn)頂標(biāo)為0，X結(jié)點(diǎn)的頂標(biāo)為它出發(fā)所有弧的最大權(quán)值，然后求相等子圖的最大匹配存在完美匹配，算法終止否則修改頂標(biāo)使得相等子圖的邊變多，有更大機(jī)會(huì)存在完美匹配考慮相等子圖不存在完美匹配時(shí)的情形算法思想關(guān)鍵：尋找好的可行頂標(biāo)，使相等子圖有完美匹配50Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為6，不是完美匹配算法在尋找增廣路失敗的同時(shí)得到了一棵匈牙利樹(shù)雖然此匈牙利樹(shù)并沒(méi)有包含未蓋點(diǎn)（因此沒(méi)有找到增廣路），但仍然含有重要信息Kuhn-Munkres算法如右圖，相等子圖的最大匹配基數(shù)為51Kuhn-Munkres算法設(shè)匈牙利樹(shù)中的X結(jié)點(diǎn)集為S，Y結(jié)點(diǎn)集為T，則S到T沒(méi)有邊（否則匈牙利樹(shù)可以繼續(xù)生長(zhǎng)）S到T的邊都是非匹配邊（想一想，為什么）但若把S中所有點(diǎn)的頂標(biāo)同時(shí)減少一個(gè)相同整數(shù)a，則S到T中可能會(huì)有新邊進(jìn)入相等子圖SSTTKuhn-Munkres算法設(shè)匈牙利樹(shù)中的X結(jié)點(diǎn)集為S，Y結(jié)52Kuhn-Munkres算法把S中所有點(diǎn)的頂標(biāo)同時(shí)減少一個(gè)相同整數(shù)a，則S到T中可能會(huì)有新邊進(jìn)入相等子圖為了保證S-T的匹配邊不離開(kāi)相等子圖，把T中所有點(diǎn)的頂標(biāo)同時(shí)增加aSSTT-a+a為保證有新邊進(jìn)入，取如果S中每個(gè)頂標(biāo)的實(shí)際減小值比這個(gè)值小則不會(huì)有新邊進(jìn)入；如果比這個(gè)值大則頂標(biāo)將變得不可行Kuhn-Munkres算法把S中所有點(diǎn)的頂標(biāo)同時(shí)減少一個(gè)相53Kuhn-Munkres算法設(shè)邊(x,y)進(jìn)入相同子圖y是未蓋點(diǎn)，則找到增廣路y和S中的點(diǎn)z匹配，則把z和y分別加入S和T中每次修改頂標(biāo)要么找到增廣路，要么使匈牙利樹(shù)增加兩個(gè)結(jié)點(diǎn)因此一共需要O(n2)次修改頂標(biāo)操作關(guān)鍵：快速修改頂標(biāo)SSTT-a+aKuhn-Munkres算法設(shè)邊(x,y)進(jìn)入相同子圖SST54頂標(biāo)的修改方法1：枚舉S和T中的每個(gè)元素，根據(jù)定義計(jì)算最小值，每次修改的時(shí)間為O(n2)，總O(n4)方法2：對(duì)于T中的每個(gè)元素y，定義松弛量則a的計(jì)算公式變?yōu)轫敇?biāo)的修改方法1：枚舉S和T中的每個(gè)元素，根據(jù)定義計(jì)算最小值55頂標(biāo)的快速修改每次增廣后用O(n2)時(shí)間計(jì)算所有點(diǎn)的初始slack，由于每次生長(zhǎng)匈牙利樹(shù)時(shí)所有S-T弧的增量相同，因此修改每個(gè)slack值只需要常數(shù)時(shí)間，計(jì)算所有slack值需要O(n)時(shí)間每次增廣后最多修改n次頂標(biāo)，因此每次增廣后修改頂標(biāo)總時(shí)間降為O(n2)，總O(n3)結(jié)論：Kuhn-Munkres算法的總時(shí)間復(fù)雜度為O(n3)頂標(biāo)的快速修改每次增廣后用O(n2)時(shí)間計(jì)算所有點(diǎn)的初始sl56應(yīng)用舉例：冰激凌加派有n種派和m種冰激凌,把第i種派與第j種冰激凌搭配可以買Wij元錢.給出第k種派的數(shù)量Pk與第k種冰激凌的數(shù)量Ik,求銷售額的最大值和最小值應(yīng)用舉例：冰激凌加派有n種派和m種冰激凌,把第i種派與第j57最大流問(wèn)題最大流問(wèn)題58流網(wǎng)絡(luò)定義一個(gè)流網(wǎng)絡(luò)(flownetwork)G=(V,E)是一個(gè)有向圖,每個(gè)邊(u,v)有一個(gè)非負(fù)容量(capacity)c(u,v)>=0.對(duì)于不在E中的(u,v),規(guī)定c(u,v)=0有兩個(gè)特殊結(jié)點(diǎn):源(source)s和匯(sink)t.假設(shè)對(duì)于任意其他點(diǎn)v,存在通路svt流網(wǎng)絡(luò)定義一個(gè)流網(wǎng)絡(luò)(flownetwork)G=(V,59流的定義流(flow)是一個(gè)邊的函數(shù)f(u,v),滿足:容量限制:f(u,v)<=c(u,v)對(duì)稱性:f(u,v)=-f(u,v)收支平衡:對(duì)于不是s或t的其他點(diǎn)u,有把整個(gè)網(wǎng)絡(luò)的流量定義為(即從s流出的流量):最大流問(wèn)題:尋找流函數(shù)f,使得網(wǎng)絡(luò)流最大流的定義流(flow)是一個(gè)邊的函數(shù)f(u,v),滿足:60等價(jià)條件1)f是最大流2)殘量網(wǎng)絡(luò)中無(wú)可增廣路3)存在某個(gè)切割(S,T),|f|=c(S,T)12:反證.若存在,可沿它增廣得到更大流23:此時(shí)不存在s-t通路.定義S為s可達(dá)結(jié)點(diǎn)集,T為可達(dá)t結(jié)點(diǎn)集,則|f|=c(S,T)(若跨越(S,T)的弧不滿載,殘量網(wǎng)絡(luò)中會(huì)有更多弧存在)31:因?yàn)閷?duì)于任意一個(gè)切割,f(S,T)=|f|,因此任意可行流量不會(huì)超過(guò)最小切割的容量等價(jià)條件1)f是最大流61Gomory-Hu樹(shù)Gomory-Hu樹(shù)62每對(duì)結(jié)點(diǎn)之間的s-t割有N個(gè)點(diǎn)M條邊的無(wú)向帶權(quán)圖，對(duì)于所有s,t(s<t)，求出s-t的最小割的容量每對(duì)結(jié)點(diǎn)之間的s-t割有N個(gè)點(diǎn)M條邊的無(wú)向帶權(quán)圖，對(duì)于所有s63Gomory-Hu樹(shù)的構(gòu)造初始時(shí)令所有點(diǎn)在同一集合中若所有點(diǎn)屬于不同點(diǎn)集，則退出，否則任找兩個(gè)點(diǎn)s,t，同時(shí)屬于某點(diǎn)集P求最小s-t割(S,T)，并把P分裂為兩個(gè)，一個(gè)是在S中的，另一個(gè)是在T中的。增加兩點(diǎn)a,a’,增加邊(a,a’),容量為割(S,T)容量，對(duì)所有跨越(S,T)的邊(u,v),從圖中刪去,并增設(shè)邊(u,a),(a’,v),,容量與邊(u,v)容量相同。轉(zhuǎn)到1Gomory-Hu樹(shù)的構(gòu)造初始時(shí)令所有點(diǎn)在同一集合中64每次調(diào)用最大流過(guò)程都使某點(diǎn)集分裂成兩個(gè)非空集合。因此N-1次調(diào)用后算法停止,這時(shí)我們共增設(shè)了N-1個(gè)點(diǎn)對(duì)，每個(gè)點(diǎn)對(duì)中的邊刪去后都會(huì)使點(diǎn)集被分成不聯(lián)通的兩部分,也就是說(shuō)這時(shí)點(diǎn)集與增設(shè)的N-1個(gè)點(diǎn)對(duì)中的邊可以構(gòu)成一棵樹(shù)。這棵樹(shù)就是Gomory-Hu樹(shù)，原圖中任兩點(diǎn)的最小割就是其在Gomory-HuTrees中對(duì)應(yīng)點(diǎn)的唯一路徑上的最小邊權(quán)。每次調(diào)用最大流過(guò)程都使某點(diǎn)集分裂成兩個(gè)非空集合。因此N-1次650,50,20,50,266最后結(jié)果最后結(jié)果67全局最小割全局最小割68全局最小割可以枚舉所有(s,t)點(diǎn)對(duì),求s-t最大流,求最小的一個(gè),但時(shí)間…先求Gomory-Hu樹(shù)，時(shí)間復(fù)雜度倒是不錯(cuò)，但編程比較麻煩…MechthildStoer,FrankWagner,ASimpleMin-CutAlgorithm,1997時(shí)間:O(VE+V2logV)全局最小割可以枚舉所有(s,t)點(diǎn)對(duì),求s-t最大流,求69定理對(duì)于G的任意兩個(gè)結(jié)點(diǎn)s和t,令G/{s,t}表示合并s和t之后的圖,則G的全局最小割可以取G的s-t最小割和G/{s,t}的最小割之間的較小者遞歸計(jì)算，則只需要求|V|次s-t最小割可是還是要求|V|次s-t最大流啊?不必,因?yàn)榭梢匀我膺x擇s-t,我們當(dāng)然是選擇一些比較好算的s-t割了!方法:MAS(MaximumAdjacencySearch)定理對(duì)于G的任意兩個(gè)結(jié)點(diǎn)s和t,令G/{s,t}表示合并s70MAS從任意結(jié)點(diǎn)a開(kāi)始生長(zhǎng)集合A,每次選擇連接A最緊的結(jié)點(diǎn)(即與A中結(jié)點(diǎn)的所有邊權(quán)和W(A,z)最大的z)加入.本次最后加入的點(diǎn)和其他點(diǎn)形成的割稱為cut-of-the-phase,每次合并最后兩個(gè)加入的點(diǎn).每階段的a可以不變也可以重選MAS從任意結(jié)點(diǎn)a開(kāi)始生長(zhǎng)集合A,每次選擇連接A最緊的結(jié)點(diǎn)71正確性定理:每階段的cut-of-the-phase是最后加入的兩個(gè)點(diǎn)的最小s-t割證明:考慮任意s-t割C.對(duì)于不是a的其他點(diǎn)v,設(shè)v和它前一個(gè)加入的點(diǎn)在C中的不同部分,稱v是active的,設(shè)Av為v之前(不含)被加入的所有點(diǎn)的集合,Cv是到v為止所有被加入點(diǎn)在C中誘導(dǎo)出的割,只需證明對(duì)任意active點(diǎn)v正確性定理:每階段的cut-of-the-phase是最后72證明對(duì)active結(jié)點(diǎn)的個(gè)數(shù)歸納.第一個(gè)active點(diǎn)出現(xiàn)時(shí),誘導(dǎo)出的割只含一條弧,不等式變?yōu)榈仁?滿足;下面考慮在u是v的下一個(gè)active結(jié)點(diǎn),則vu根據(jù)v的選擇方式,W(Av,u)<=W(Av,v),根據(jù)歸納假設(shè),W(Av,v)<=W(Cv)根據(jù)傳遞性,W(Au,u)<=W(Cv)+W(Au\Av,u)由圖上可知,這兩部分是W(Cu)的子集,故W(Av,u)<=W(Cu)完成歸納假設(shè).注意到t總是active的…證明對(duì)active結(jié)點(diǎn)的個(gè)數(shù)歸納.第一個(gè)active點(diǎn)出現(xiàn)73時(shí)間復(fù)雜度顯然每個(gè)phase時(shí)間相同,一共|V|次每個(gè)phase,每個(gè)不在A中的結(jié)點(diǎn)按”與A的邊權(quán)和”為關(guān)鍵字組成優(yōu)先隊(duì)列|V|次ExtractMax:取出最緊的點(diǎn)加入A|E|次IncreaseKey:每次選擇結(jié)點(diǎn)u加入后,所有邊uv對(duì)應(yīng)的v(在A外)的關(guān)鍵字要增加w(u,v)二叉堆:O(ElogV)時(shí)間復(fù)雜度顯然每個(gè)phase時(shí)間相同,一共|V|次74最大流算法——最短增廣路最大流算法——最短增廣路75概述每次找邊數(shù)最少的增廣路進(jìn)行增廣定理：最多增廣O(nm)次Edmonds-Karp：每次BFS找增廣路，無(wú)需維護(hù)附加信息Dinic：多次BFS構(gòu)造層次圖，DFS找增廣路。附加信息：層次（起點(diǎn)到u的距離值）ISAP：動(dòng)態(tài)維護(hù)距離標(biāo)號(hào)（重標(biāo)號(hào)），DFS找增廣路。距離標(biāo)號(hào)是u到匯點(diǎn)的距離下限。選擇：熟練編寫Dinic和ISAP之一即可概述每次找邊數(shù)最少的增廣路進(jìn)行增廣76嚴(yán)格來(lái)說(shuō)，SAP是一類算法的集合，Edmonds-Karp、Dinic和ISAP都屬于它。網(wǎng)絡(luò)文章中的SAP基本都是特指ISAP。Dinic一般采用多路增廣，同時(shí)用手工模擬棧，而不是遞歸找增廣路當(dāng)效率要求不高時(shí)每次只找一條路，迭代即可ISAP初始距離標(biāo)號(hào)可以統(tǒng)一設(shè)為0，也可以用BFS找，效率相差不大一定要用GAP優(yōu)化建議用當(dāng)前弧優(yōu)化，迭代實(shí)現(xiàn)嚴(yán)格來(lái)說(shuō)，SAP是一類算法的集合，Edmonds-Karp、77ISAP距離標(biāo)號(hào)d(i)是頂點(diǎn)到非負(fù)整數(shù)的映射,它的動(dòng)機(jī)是:描述i到t的最短路下界,它必須滿足以下條件:d(t)=0d(i)<=d(j)+1,對(duì)于所有殘量網(wǎng)絡(luò)中的邊(i,j)如果d(s)>=n,則殘量網(wǎng)絡(luò)中一定沒(méi)有s-t路d(i)=d(j)+1的弧(i,j)稱為允許弧,允許路是最短路,強(qiáng)制走允許路ISAP距離標(biāo)號(hào)d(i)是頂點(diǎn)到非負(fù)整數(shù)的映射,它的動(dòng)機(jī)是78可以證明,如果一條弧是非允許弧,則只要d(i)不變,它不可能再次變成允許弧因此如果掃描到最后一條弧還是沒(méi)有找到允許弧,必須對(duì)i進(jìn)行重新標(biāo)號(hào):取d(i)=min{d(j)+1|(i,j)在Gf中}并設(shè)當(dāng)前弧為第一條弧,重新標(biāo)號(hào)以后往回走一步而不要繼續(xù)找允許弧,因?yàn)楫?dāng)前路徑已經(jīng)不是允許路了（GAP優(yōu)化）假設(shè)重標(biāo)號(hào)是把x改成了y，檢查是否還有結(jié)點(diǎn)的距離標(biāo)號(hào)為x，沒(méi)有的話終止算法可以證明,如果一條弧是非允許弧,則只要d(i)不變,它79最大流算法——預(yù)流推進(jìn)最大流算法——預(yù)流推進(jìn)80預(yù)流推進(jìn)算法并不檢查整個(gè)網(wǎng)絡(luò),而是每次考慮一個(gè)結(jié)點(diǎn),在殘量網(wǎng)絡(luò)中只檢查它的鄰居預(yù)流推進(jìn)算法并不始終保持流量平衡條件,而是生成預(yù)流。預(yù)流也滿足對(duì)稱性和容量限制，和流不同的是：流進(jìn)每個(gè)非s點(diǎn)的凈流非負(fù)(蓄勢(shì)待發(fā),等著流出)。記e(u)為點(diǎn)u的盈余自上而下的水流，邊是管道，點(diǎn)是連接口每個(gè)點(diǎn)有一個(gè)小型蓄水池用于儲(chǔ)存盈余水量隨著算法進(jìn)行，每個(gè)點(diǎn)的高度逐漸增大水往低處流，直到?jīng)]有水了或者弧滿載(push)；如果有水卻流不動(dòng),需要抬高水位,讓它可以繼續(xù)往低處流(relabel)預(yù)流推進(jìn)算法并不檢查整個(gè)網(wǎng)絡(luò),而是每次考慮一個(gè)結(jié)點(diǎn),在殘81水源高度固定為|V|,匯的高度固定為0,其他點(diǎn)的高度初始為0,隨著時(shí)間推移慢慢增加首先盡量多的從水源把水”推”出來(lái),即讓s出發(fā)的所有弧滿載.水流入某個(gè)結(jié)點(diǎn)u后,進(jìn)入該結(jié)點(diǎn)的蓄水池如果u出發(fā)有到達(dá)更低點(diǎn)v的非飽和弧,把盡量多的水推入v(push過(guò)程)如果u出發(fā)的所有非飽和弧都連接著與u水平甚至更高的點(diǎn),把u抬高直到可以推(relabel過(guò)程)最終,所有能流到t的水都已經(jīng)流到t了,把所有點(diǎn)的蓄水池里的水都倒回s(只需把水位抬得比s還高)水源高度固定為|V|,匯的高度固定為0,其他點(diǎn)的高度初始82Push操作基本操作PUSH(u,v)的條件u有盈余（e[u]>0），且(u,v)在殘量網(wǎng)絡(luò)中，且h(u)=h(v)+1推進(jìn)量:min{e[u],residual(u,v)}飽和推進(jìn)(水太多)非飽和推進(jìn)(水不夠)Push的效果是修改e（盈余）和f（流量）進(jìn)行非飽和推進(jìn)后,盈余e[u]變?yōu)?高度函數(shù)，類似于距離標(biāo)號(hào)初始h(s)=|V|,其他h(u)=0Push操作基本操作PUSH(u,v)的條件高度函數(shù)，類似于83Relabel操作基本操作RELABEL(u)的條件u有盈余的殘量網(wǎng)絡(luò)中的所有弧(u,v)滿足h[u]<=h[v]即:雖然u有盈余,可是由于位置太低,無(wú)法進(jìn)行PUSH操作,需要RELABEL注意:s和t是不會(huì)有盈余的,因此不需要RELABEL既然u有盈余,在殘量網(wǎng)絡(luò)中,u出發(fā)一定有弧操作：增加h[u]h[u]=1+min{h[v]|(u,v)在殘量網(wǎng)絡(luò))}Relabel操作基本操作RELABEL(u)的條件84RELABEL-TO-FRONT算法隊(duì)列：維護(hù)結(jié)點(diǎn)列表,從頭開(kāi)始掃描,每次對(duì)一個(gè)盈余結(jié)點(diǎn)進(jìn)行discharge(即連續(xù)進(jìn)行push和relabel,直到它沒(méi)有盈余)，relabel時(shí)放到列表尾部當(dāng)前弧優(yōu)化：假設(shè)v為當(dāng)前弧，V為空,則需要RELABEL(u)V非空且(u,v)是允許弧,則PUSH(u,v)V非空且(u,v)不是允許弧,無(wú)操作RELABEL之后加入GAP優(yōu)化非飽和推進(jìn)減少，時(shí)間復(fù)雜度為O(V3)RELABEL-TO-FRONT算法隊(duì)列：維護(hù)結(jié)點(diǎn)列表,從85最小費(fèi)用流問(wèn)題最小費(fèi)用流問(wèn)題86最小費(fèi)用流如下圖,弧上除了網(wǎng)絡(luò)外還有一個(gè)費(fèi)用值總費(fèi)用等于每條弧的流量與費(fèi)用的乘積最小費(fèi)用流如下圖,弧上除了網(wǎng)絡(luò)外還有一個(gè)費(fèi)用值87殘量網(wǎng)絡(luò)殘量網(wǎng)絡(luò)N’=(G’,c’,s,t)c’的定義同不帶費(fèi)用的網(wǎng)絡(luò)流問(wèn)題費(fèi)用定義正向弧費(fèi)用為w(e)反向弧費(fèi)用為-w(e)殘量網(wǎng)絡(luò)殘量網(wǎng)絡(luò)N’=(G’,c’,s,t)88消圈定理消圈定理:流量為f的可行流x為流量為f的最小費(fèi)用流當(dāng)且僅當(dāng)x沒(méi)有負(fù)費(fèi)用增廣圈必要性顯然，用反證法證明充分性。假設(shè)存在不同的可行流x0使得它的費(fèi)用比x更低，則它們的差x1=x0-x是網(wǎng)絡(luò)中的負(fù)費(fèi)用循環(huán)流。既然是循環(huán)流，x1一定可以分解為至多m個(gè)非零圈流之和，則它們中至少有一個(gè)圈是負(fù)費(fèi)用的（有限個(gè)非負(fù)費(fèi)用之和仍是非負(fù)的），這個(gè)圈就是題目中非負(fù)增廣圈，矛盾消圈定理消圈定理:流量為f的可行流x為流量為f的最小費(fèi)用流89消圈算法經(jīng)典的消圈算法(Klein):利用bellman-ford找負(fù)圈,最壞情況需要迭代O(C)次每次用O(nm)時(shí)間找平均費(fèi)用最小的增廣圈進(jìn)行增廣,則對(duì)于整數(shù)權(quán)來(lái)說(shuō)最多迭代O(nmlog(nC)),而對(duì)于任意實(shí)數(shù)權(quán)來(lái)說(shuō)最多迭代O(nm2logn)次結(jié)論:雖然是強(qiáng)多項(xiàng)式時(shí)間復(fù)雜度,但階太高,不實(shí)用消圈算法經(jīng)典的消圈算法(Klein):利用bellman-90連續(xù)最短路算法由Jewell(1958),Iri(1960),Busacker和Gowen(1961)等人獨(dú)立提出算法是迭代式的,流量為v時(shí)的當(dāng)前費(fèi)用流是流量為v的最小費(fèi)用流最小費(fèi)用增廣路是殘量網(wǎng)絡(luò)中最短的s-t路.由于殘量網(wǎng)絡(luò)中的費(fèi)用有正有負(fù),所以最短路只能用bellman-ford算法計(jì)算,每次需要O(mn)時(shí)間,假設(shè)增廣k次,則時(shí)間復(fù)雜度為O(kn3),對(duì)稀疏圖為O(knm)連續(xù)最短路算法由Jewell(1958),Iri(196091正確性證明如下圖,箭頭都代表多步到達(dá),w是負(fù)圈,故P(i->a->b->c->j)+P(j->i)<0,因此P(i->a->b->c->j)<P(i->j)sijtabcPW正確性證明如下圖,箭頭都代表多步到達(dá),w是負(fù)圈,故si92假設(shè)增廣前s到u的距離為d(u),增廣后的費(fèi)用函數(shù)為w(e),對(duì)于弧e=uv定義一個(gè)新的權(quán)值w*(e)=w(e)+d(u)–d(v),則對(duì)于任意s-t路X,有w*(X)=w(X)–d(x),即對(duì)于權(quán)函數(shù)w(e),w*(e),從s出發(fā)的單源最短路樹(shù)完全一樣改進(jìn)算法:用w*(e)=w(e)+d(u)-d(v)作為權(quán)函數(shù)計(jì)算單源最短路d*(x),然后計(jì)算出真正的新最短路注意到w*(e)是非負(fù)的,所以可以用dijkstra實(shí)現(xiàn).為什么是非負(fù)的?因?yàn)槿绻鹷*(e)=w(e)+d(u)-d(v)<0,有d(v)>d(u)+w(e)和d(u)是最短距離矛盾時(shí)間復(fù)雜度降為O(kn2),稀疏圖O(kmlogn)假設(shè)增廣前s到u的距離為d(u),增廣后的費(fèi)用函數(shù)為w(e93應(yīng)用：特殊二分圖最佳匹配每個(gè)X點(diǎn)有一個(gè)權(quán)值，最后要求所有被匹配到的X點(diǎn)的權(quán)和盡量大算法：將X點(diǎn)按照權(quán)值從大到小排序，套用二分圖最大基數(shù)匹配框架，先從權(quán)值大的點(diǎn)開(kāi)始增廣，得到的就是最優(yōu)解想一想，為什么應(yīng)用：特殊二分圖最佳匹配每個(gè)X點(diǎn)有一個(gè)權(quán)值，最后要求所有被匹94最小樹(shù)型圖最小樹(shù)型圖95朱-劉算法（固定根）首先消除自環(huán)，顯然自環(huán)不在最小樹(shù)形圖中。然后判定是否存在最小樹(shù)形圖，以根為起點(diǎn)DFS一遍即可。對(duì)于除根外的每個(gè)頂點(diǎn)，選擇一條權(quán)最小的入邊。如果選出來(lái)的V-1條邊不構(gòu)成環(huán)，則可以證明這些邊就是滿足要求的答案。否則收縮每個(gè)環(huán)，調(diào)整權(quán)值后求新圖的最小樹(shù)形圖朱-劉算法（固定根）首先消除自環(huán)，顯然自環(huán)不在最小樹(shù)形圖中。96453-4-3-5從新結(jié)點(diǎn)出去的邊權(quán)不變?nèi)绻昧藦耐饷孢M(jìn)來(lái)的邊，就得刪除里面的邊最終答案加上人工點(diǎn)的權(quán)和453-4-3-5從新結(jié)點(diǎn)出去的邊權(quán)不變97應(yīng)用：舉辦比賽給出一些有向邊，邊有帶寬，還有一個(gè)修建費(fèi)用，然后開(kāi)始的時(shí)候你有cost錢問(wèn)你怎么修建一個(gè)從0到達(dá)其他所有點(diǎn)的網(wǎng)絡(luò)，使得所有網(wǎng)絡(luò)中最小的帶寬值最大應(yīng)用：舉辦比賽給出一些有向邊，邊有帶寬，還有一個(gè)修建費(fèi)用，然98題目分析與討論題目分析與討論991.太空旅行太空里有n個(gè)星球，你的任務(wù)是用最少的步數(shù)從星球S到達(dá)星球T。每次可以從一個(gè)星球跳到另一個(gè)星球，但并不是所有n(n-1)種跳法都是可行的。所有頂點(diǎn)一共有k個(gè)“禁止區(qū)間”，其中每個(gè)禁止區(qū)間用(U,V1,V2)表示，即從星球U出發(fā)，不可以直接跳到V1,V1+1,V1+2,…,V2這些星球。1.太空旅行太空里有n個(gè)星球，你的任務(wù)是用最少的步數(shù)從星球S1002.有向圖D和E給一個(gè)n個(gè)結(jié)點(diǎn)的有向圖D，你可以構(gòu)造這樣一個(gè)圖E：D的每條邊對(duì)應(yīng)E的一個(gè)結(jié)點(diǎn)（比如，若D有一條邊uv，則E有個(gè)結(jié)點(diǎn)的名字叫uv），對(duì)于D的兩條邊uv和vw，E中的兩個(gè)結(jié)點(diǎn)uv和vw之間連一條有向邊。E中不包含其他邊。給定圖E，你的任務(wù)是判斷是否存在對(duì)應(yīng)的圖D。2.有向圖D和E給一個(gè)n個(gè)結(jié)點(diǎn)的有向圖D，你可以構(gòu)造這樣一個(gè)1013.01串處理機(jī)給M個(gè)長(zhǎng)度為N的串，包含字符0,1或星號(hào)*。每個(gè)串最多包含一個(gè)星號(hào)。比如01*表示010和011。用盡量少的指令處理所有串，其中每個(gè)指令也是一個(gè)長(zhǎng)度為N，包含0,1或星號(hào)，且最多包含一個(gè)星號(hào)的串（指令10*處理100和101）。例如：{*01,100,011}至少需要兩條指令10*和0*1。N<=10,M<=1000。3.01串處理機(jī)給M個(gè)長(zhǎng)度為N的串，包含字符0,1或星號(hào)*。1024.帶寬難題給一個(gè)無(wú)向圖G，令T(u,v)為u到v的最大流流量。給定矩陣T，求滿足條件的邊數(shù)最少的無(wú)向圖G。T(u,u)總是0，T(u,v)總是等于T(v,u)，