圖論中的圈與塊無(wú)向圖的最小環(huán)第一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義2基本概念圈(環(huán))割點(diǎn)割邊(橋)塊強(qiáng)連通子圖(強(qiáng)連通分量(支,塊))第二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義3圈及其相關(guān)知識(shí)MST(最小生成樹(shù))另類算法最小環(huán)問(wèn)題第三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義4MST另類算法任意構(gòu)造一棵原圖的生成樹(shù)，然后不斷的添邊，并刪除新生成的環(huán)上的最大邊。1017253算法證明?第四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義5水管局長(zhǎng)(1)給定一張帶權(quán)無(wú)向連通圖，定義max(p)為路徑p上的最大邊，min(u,v)為連接u和v的所有路徑中，max(p)的最小值。動(dòng)態(tài)的做如下兩個(gè)操作：1：詢問(wèn)某兩個(gè)點(diǎn)之間的min(u,v)2：刪除一條邊你的任務(wù)是對(duì)于每個(gè)詢問(wèn)，輸出min(u,v)的值。(WC2006)第五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義6水管局長(zhǎng)(2)數(shù)據(jù)范圍約定結(jié)點(diǎn)個(gè)數(shù)N≤1000圖中的邊數(shù)M≤100000詢問(wèn)次數(shù)Q≤100000刪邊次數(shù)D≤5000第六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義7水管局長(zhǎng)(3)根據(jù)kruskal算法可以知道，最小生成樹(shù)上的連接兩點(diǎn)之間的唯一路徑一定是最大邊最小的那么，只要維護(hù)一棵圖的最小生成樹(shù)，那么就可以在O(N)的時(shí)間內(nèi)回答每一個(gè)min(u,v)的詢問(wèn)不斷的刪邊然后維護(hù)最小生成樹(shù)？第七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義8水管局長(zhǎng)(4)通過(guò)刪邊的形式我們似乎很難維護(hù)一張圖的最小生成樹(shù)根據(jù)剛才提到的MST的另類做法，我們反向處理它的每個(gè)操作，也就是先刪除所有要?jiǎng)h的邊，然后再逆向添邊并回答min(u,v)于是該問(wèn)題就可以用另類MST算法解決了第八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義9水管局長(zhǎng)(5)這里涉及到一些圖與樹(shù)的存儲(chǔ)操作，如何在O(N)的時(shí)間內(nèi)找到環(huán)上最大邊，并維護(hù)一棵最小生成樹(shù)呢？如果采取鄰接表的存儲(chǔ)方式來(lái)記錄一棵最小生成樹(shù)，從添加的邊的某個(gè)點(diǎn)開(kāi)始遍歷整棵樹(shù)，尋找出環(huán)上的最大邊，雖然理論復(fù)雜度是O(N)的，但是有很多的冗余第九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義10水管局長(zhǎng)(6)這里我們采取父親表示法來(lái)存儲(chǔ)一棵最小生成樹(shù)，如圖所示：現(xiàn)在添加入一條紅色的邊AB我們根據(jù)被刪邊所在的位置來(lái)決定AB的定向如果被刪邊在B到LCA(A,B){A和B的最近公共祖先}的那條路徑上，則定義AB的方向?yàn)锽->A，即A是B的父親，并將被刪邊到B的這條路徑上的所有邊反向(同理可得被刪邊在A到LCA(A,B)的那條路徑上的情況)AB第十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義11小H的聚會(huì)(1)給定每個(gè)節(jié)點(diǎn)的度限制，求在滿足所有度限制的條件下的最大生成樹(shù)。(NOI2005)這是一道提交答案式的題目，對(duì)于后面的幾個(gè)較大的數(shù)據(jù)，用另類MST算法對(duì)你的解進(jìn)行調(diào)整也能取得不錯(cuò)的效果！第十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義12最小環(huán)問(wèn)題雖然涉及到要求最小環(huán)的題目并不多(Ural1004Sightseeingtrip)，但是下面介紹的一些求最小環(huán)的算法也會(huì)對(duì)你有一定的啟示意義有向帶權(quán)圖的最小環(huán)問(wèn)題(直接用floyd算法可解)無(wú)向帶權(quán)圖的最小環(huán)問(wèn)題第十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義13樸素算法令e(u,v)表示u和v之間的連邊，再令min(u,v)表示，刪除u和v之間的連邊之后，u和v之間的最短路最小環(huán)則是min(u,v)+e(u,v)時(shí)間復(fù)雜度是EV2第十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義14一個(gè)錯(cuò)誤的算法預(yù)處理出任意兩點(diǎn)之間的最短路徑，記作min(u,v)枚舉三個(gè)點(diǎn)w,u,v，最小環(huán)則是min(u,w)+min(w,v)+e(u,v)的最小值如果考慮min(u,w)包含邊u-v的情況？討論：是否有解決的方法？第十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義15改進(jìn)算法在floyd的同時(shí)，順便算出最小環(huán)g[i][j]=i,j之間的邊長(zhǎng)dist:=g;fork:=1tondobeginfori:=1tok-1doforj:=i+1tok-1doanswer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);fori:=1tondoforj:=1tondodist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);end;算法證明？第十五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義16塊及其相關(guān)知識(shí)DFS算法割點(diǎn)(一般對(duì)于無(wú)向圖而言)割邊(一般對(duì)于無(wú)向圖而言)塊(一般對(duì)于無(wú)向圖而言)強(qiáng)連通子圖(一般對(duì)于有向圖而言)第十六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義17DFS算法1973年，Hopcroft和Tarjan設(shè)計(jì)了一個(gè)有效的DFS算法PROCEDUREDFS(v);begin inc(sign); dfn[v]:=sign;//給v按照訪問(wèn)順序的先后標(biāo)號(hào)為sign for尋找一個(gè)v的相鄰節(jié)點(diǎn)u if邊uv沒(méi)有被標(biāo)記過(guò)then begin標(biāo)記邊uv; 給邊定向v→u;如果u被標(biāo)記過(guò),記uv為父子邊,否則記uv為返祖邊 ifu未被標(biāo)記thenDFS(u); end;end;第十七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義18DFS算法父子邊用黑色標(biāo)記，返祖邊用紅色標(biāo)記如下圖，除掉返祖邊之后，我們可以把它看作一棵DFS樹(shù)1234567第十八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義19割點(diǎn)G是連通圖，v∈V(G)，G–v不再連通，則稱v是G的割頂。第十九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義20求割點(diǎn)的算法我們通過(guò)DFS把無(wú)向圖定向成有向圖，定義每個(gè)頂?shù)囊粋€(gè)lowlink參數(shù)，lowlink[v]表示沿v出發(fā)的有向軌能夠到達(dá)的點(diǎn)u中，dfn[u]的值的最小值。(經(jīng)過(guò)返祖邊后則停止)1.12.13.24.25.26.17.7第二十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義21三個(gè)定理定理1：DFS中，e=ab是返祖邊，那么要么a是b的祖先，要么a是b的后代子孫。定理2：DFS中，e=uv是父子邊，且dfn[u]>1，lowlink[v]≥dfn[u]，則u是割點(diǎn)。定理3：DFS的根r是割點(diǎn)的充要條件是：至少有2條以r為尾(從r出發(fā))的父子邊證明？證明？證明？第二十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義22程序代碼PROCEDUREDFS(v);begin inc(sign);dfn[v]:=sign;//給v按照訪問(wèn)順序的先后標(biāo)號(hào)為sign lowlink[v]:=sign;//給lowlink[v]賦初始值 for尋找一個(gè)v的相鄰節(jié)點(diǎn)u if邊uv沒(méi)有被標(biāo)記過(guò)then begin 標(biāo)記邊uv; 給邊定向v→u; ifu未被標(biāo)記過(guò)then begin DFS(u);//uv是父子邊，遞歸訪問(wèn) lowlink[v]:=min(lowlink[v],lowlink[u]);

iflowlink[u]>=dfn[v]thenv是割點(diǎn)

end else lowlink[v]:=min(lowlink[v],dfn[u]);//uv是返祖邊 end;end;第二十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義23割邊G是連通圖，e∈E(G)，G–e不再連通，則稱e是G的割邊，亦稱做橋。

第二十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義24求割邊的算法與割點(diǎn)類似的，我們定義lowlink和dfn。父子邊e=u→v，當(dāng)且僅當(dāng)lowlink[v]>dfn[u]的時(shí)候，e是割邊。我們可以根據(jù)割點(diǎn)算法的證明類似的證明割邊算法的正確性。第二十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義25程序代碼PROCEDUREDFS(v);begin inc(sign);dfn[v]:=sign;//給v按照訪問(wèn)順序的先后標(biāo)號(hào)為sign lowlink[v]:=sign;//給lowlink[v]賦初始值 for尋找一個(gè)v的相鄰節(jié)點(diǎn)u if邊uv沒(méi)有被標(biāo)記過(guò)then begin 標(biāo)記邊uv; 給邊定向v→u; ifu未被標(biāo)記過(guò)then begin DFS(u);//uv是父子邊，遞歸訪問(wèn) lowlink[v]:=min(lowlink[v],lowlink[u]);

iflowlink[u]>dfn[v]thenvu是割邊

end else lowlink[v]:=min(lowlink[v],dfn[u]);//uv是返祖邊 end;end;第二十五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義26割點(diǎn)與割邊猜想：兩個(gè)割點(diǎn)之間的邊是否是割邊?割邊的兩個(gè)端點(diǎn)是否是割點(diǎn)？都錯(cuò)！第二十六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義27嗅探器(1)在無(wú)向圖中尋找出所有的滿足下面條件的點(diǎn)：割掉這個(gè)點(diǎn)之后，能夠使得一開(kāi)始給定的兩個(gè)點(diǎn)a和b不連通，割掉的點(diǎn)不能是a或者b。(ZJOI2004)ab第二十七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義28嗅探器(2)數(shù)據(jù)范圍約定結(jié)點(diǎn)個(gè)數(shù)N≤100邊數(shù)M≤N*(N-1)/2第二十八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義29嗅探器(3)樸素算法：枚舉每個(gè)點(diǎn)，刪除它，然后判斷a和b是否連通，時(shí)間復(fù)雜度O(NM)如果數(shù)據(jù)范圍擴(kuò)大，該算法就失敗了！第二十九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義30嗅探器(4)題目要求的點(diǎn)一定是圖中的割點(diǎn)，但是圖中的割點(diǎn)不一定題目要求的點(diǎn)。如上圖中的藍(lán)色點(diǎn)，它雖然是圖中的割點(diǎn)，但是割掉它之后卻不能使a和b不連通由于a點(diǎn)肯定不是我們所求的點(diǎn)，所以可以以a為根開(kāi)始DFS遍歷整張圖。對(duì)于生成的DFS樹(shù)，如果點(diǎn)v是割點(diǎn)，如果以他為根的子樹(shù)中存在點(diǎn)b，那么該點(diǎn)是問(wèn)題所求的點(diǎn)。第三十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義31嗅探器(5)時(shí)間復(fù)雜度是O(M)的如圖，藍(lán)色的點(diǎn)表示問(wèn)題的答案，黃色的點(diǎn)雖然是圖的割點(diǎn)，但卻不是問(wèn)題要求的答案ab第三十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義32關(guān)鍵網(wǎng)線(1)無(wú)向連通圖中，某些點(diǎn)具有A屬性，某些點(diǎn)具有B屬性。請(qǐng)問(wèn)哪些邊割掉之后能夠使得某個(gè)連通區(qū)域內(nèi)沒(méi)有A屬性的點(diǎn)或者沒(méi)有B屬性的點(diǎn)。(CEOI2005)數(shù)據(jù)范圍約定結(jié)點(diǎn)個(gè)數(shù)N≤100000邊數(shù)M≤1000000第三十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義33關(guān)鍵網(wǎng)線(2)樸素算法：枚舉每條邊，刪除它，然后判斷是否有獨(dú)立出來(lái)的連通區(qū)域內(nèi)沒(méi)有A屬性或者沒(méi)有B屬性。復(fù)雜度O(M2)當(dāng)然，這個(gè)復(fù)雜度太大了！第三十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義34關(guān)鍵網(wǎng)線(3)正如嗅探器一樣，題目要求的邊一定是原圖中的割邊，但是原圖中的割邊卻不一定是題目中要求的邊。設(shè)A種屬性總共有SUMA個(gè)，B中屬性總共有SUMB個(gè)。和嗅探器類似的，如果邊e=u→v是割邊，且以v為根的子樹(shù)中，A種屬性的數(shù)目為0或者為SUMA，或者B種屬性的數(shù)目為0或者為SUMB，那么e就是題目要求的邊。第三十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義35關(guān)鍵網(wǎng)線(4)下圖中，藍(lán)色的邊表示題目要求的邊，黃色的邊表示雖然是圖中的割邊，但不是題目要求的邊。ABAAAAAAABB第三十五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義36塊沒(méi)有割點(diǎn)的圖叫2-連通圖，亦稱做塊，G中成塊的極大子圖叫做G的塊。把每個(gè)塊收縮成一個(gè)點(diǎn)，就得到一棵樹(shù)，它的邊就是橋。第三十六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義37求塊的算法在求割點(diǎn)的算法中，當(dāng)結(jié)點(diǎn)u的所有鄰邊都被訪問(wèn)過(guò)之后，如果lowlink[u]=dfn[u]，我們把u下方的整塊和u導(dǎo)出作為圖中的一個(gè)塊。這里需要用一個(gè)棧來(lái)表示哪些元素是u代表的塊。第三十七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義38程序代碼PROCEDUREDFS(v);begin inc(sign);dfn[v]:=sign;//給v按照訪問(wèn)順序的先后標(biāo)號(hào)為sign lowlink[v]:=sign;//給lowlink[v]賦初始值 inc(tot);stack[tot]:=v;//v點(diǎn)進(jìn)棧 for尋找一個(gè)v的相鄰節(jié)點(diǎn)u if邊uv沒(méi)有被標(biāo)記過(guò)then begin 標(biāo)記邊uv; 給邊定向v→u; ifu未被標(biāo)記過(guò)then begin DFS(u);//uv是父子邊，遞歸訪問(wèn)第三十八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義39程序代碼 lowlink[v]:=min(lowlink[v],lowlink[u]); end else lowlink[v]:=min(lowlink[v],dfn[u]);//uv是返祖邊 end; iflowlink[v]=dfn[v]then begin 塊數(shù)目number+1; repeat 標(biāo)記stack[tot]這個(gè)點(diǎn)為number; dec(tot);//點(diǎn)出棧 untilstack[tot+1]=v; end;end;第三十九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義40新修公路(1)給出一張簡(jiǎn)單無(wú)向圖，問(wèn)最少添加幾條邊能夠使得原圖中沒(méi)有割邊。(CEOI2000)數(shù)據(jù)范圍約定結(jié)點(diǎn)個(gè)數(shù)N≤2500邊數(shù)M≤20000第四十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義41新修公路(2)為了簡(jiǎn)化數(shù)據(jù)關(guān)系，我們先將原圖收縮，變成一棵樹(shù)，容易知道的是，剩下的任務(wù)就是添最少的邊，使得樹(shù)成為一個(gè)塊。(樹(shù)中的兩個(gè)結(jié)點(diǎn)之間連邊相當(dāng)于原圖中兩個(gè)塊中分別任意取點(diǎn)連在一起)猜想：每添一條邊，就選擇樹(shù)中的兩個(gè)葉子結(jié)點(diǎn)，將它們連起來(lái)，于是最少的添邊數(shù)目就是(葉子結(jié)點(diǎn)個(gè)數(shù)+1)/2第四十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義42新修公路(3)如圖所示，點(diǎn)代表了原圖中的一個(gè)塊，它們之間的連邊是割邊。連接a與c，b與d之后，圖中就沒(méi)有割邊了。abcd第四十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義43新修公路(4)但并不是任意連接兩個(gè)葉子結(jié)點(diǎn)就可以達(dá)到目標(biāo)。假如連接了a與b，c與d，原圖并沒(méi)有變成一個(gè)塊。abcd第四十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義44新修公路(5)進(jìn)一步分析剛才的算法，每次連接兩個(gè)葉子結(jié)點(diǎn)之后，把新生成的圈壓縮成為一個(gè)點(diǎn)，以前和圈上的點(diǎn)關(guān)聯(lián)的點(diǎn)，都和新生成的這個(gè)“壓縮點(diǎn)”相關(guān)聯(lián)。于是原來(lái)的樹(shù)在添加一條邊之后，又變回了一棵樹(shù)。第四十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義45新修公路(6)在連接a與c之后，新生成的樹(shù)只剩下2個(gè)葉子結(jié)點(diǎn)；連接b與d之后，樹(shù)就被壓縮成了一個(gè)點(diǎn)。abcdbd第四十五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義46新修公路(7)而如果先連接a與b，那么新生成的樹(shù)會(huì)剩下3個(gè)葉子結(jié)點(diǎn)，連接c與d之后，樹(shù)中還剩2個(gè)葉子結(jié)點(diǎn)，所以這種連接方法還需要多連一條邊。現(xiàn)在的問(wèn)題是，是否一定能找出這樣子的兩個(gè)葉子結(jié)點(diǎn)，使得壓縮成的點(diǎn)不會(huì)成為新的葉子節(jié)點(diǎn)呢？第四十六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義47新修公路(8)連接的兩個(gè)點(diǎn)的那條樹(shù)中的唯一路徑上，如果除了它們的最近公共祖先到自己的父親有連邊以外，其他的結(jié)點(diǎn)沒(méi)有別的分叉，那么連接這兩個(gè)點(diǎn)之后縮圈得到的點(diǎn)將會(huì)是一個(gè)葉子結(jié)點(diǎn)。假設(shè)圖中的任意兩個(gè)葉子連接之后，都會(huì)多產(chǎn)生一個(gè)葉子結(jié)點(diǎn)。當(dāng)圖中的葉子結(jié)點(diǎn)是2個(gè)或者3個(gè)的時(shí)候，怎么連都沒(méi)有區(qū)別。第四十七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義48新修公路(9)當(dāng)圖中的葉子結(jié)點(diǎn)有4個(gè)的時(shí)候，a和b到它們的最近公共祖先都沒(méi)有別的分叉，且c和d到它們的最近公共祖先沒(méi)有別的分叉，可以知道，a和c到它們的最近公共祖先上一定有分叉。這個(gè)與假設(shè)矛盾。所以我們總能找到兩個(gè)葉子結(jié)點(diǎn)，使得它們連邊之后縮成的樹(shù)不會(huì)新產(chǎn)生葉子結(jié)點(diǎn)。第四十八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義49新修公路(10)具體實(shí)現(xiàn)：首先一個(gè)問(wèn)題是會(huì)碰到圖的壓縮，一個(gè)簡(jiǎn)單易行的方法是，新建一棵樹(shù)來(lái)表示壓縮過(guò)之后的圖。接著還會(huì)碰到一個(gè)縮圈的問(wèn)題，怎么實(shí)現(xiàn)這一個(gè)環(huán)節(jié)？是否需要重新建樹(shù)？可以采取標(biāo)號(hào)法，當(dāng)縮一個(gè)圈的時(shí)候，在圈上取一個(gè)代表點(diǎn)，并把其他的點(diǎn)都標(biāo)記為該代表點(diǎn)。一個(gè)潛在的問(wèn)題是，壓縮成的點(diǎn)可能還會(huì)被再次壓縮，那么標(biāo)記的時(shí)候就比較麻煩了。所以這里可以用并查集來(lái)實(shí)現(xiàn)標(biāo)號(hào)這一步。第四十九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義50新修公路(11)算法流程：(1)求出圖中的所有塊，建立一棵代表樹(shù)(2)挑出2個(gè)葉子結(jié)點(diǎn)，使得連接他們之間的唯一路徑上的分叉數(shù)目最多(3)連接這兩個(gè)葉子結(jié)點(diǎn)，并壓縮新生成的圈，得到一棵新的樹(shù)(4)如果樹(shù)中剩下一個(gè)葉子結(jié)點(diǎn)和一個(gè)根結(jié)點(diǎn)，直接連接它們，算法結(jié)束；如果樹(shù)已經(jīng)成為一個(gè)點(diǎn)，算法結(jié)束，否則轉(zhuǎn)(2)第五十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義51有向圖的DFS有向圖的DFS與無(wú)向圖的DFS的區(qū)別在于搜索只能順邊的方向進(jìn)行，所以有向圖的DFS不止一個(gè)根，因?yàn)閺哪硞€(gè)結(jié)點(diǎn)開(kāi)始不一定就能走完所有的點(diǎn)。另外，有向圖的DFS除了產(chǎn)生父子邊和返祖邊以外，還會(huì)有橫叉邊。我們這樣定義它：u和v在已形成的DFS森林中沒(méi)有直系上下關(guān)系，并且有dfn[v]>dfn[u]，則稱e=uv是橫叉邊。注意，沒(méi)有dfn[v]<dfn[u]這種橫叉邊。第五十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義52連通與強(qiáng)連通圖定義：將所有有向邊改為無(wú)向邊，如果該無(wú)向圖是連通的，那么原有向圖也稱之為連通圖。對(duì)于圖中的任意兩個(gè)點(diǎn)A和B，同時(shí)存在一條從A到B的路徑和一條從B到A的路徑，則稱該圖為強(qiáng)連通圖。對(duì)于一個(gè)連通的無(wú)向圖，他是一個(gè)強(qiáng)連通圖，這里著重介紹一下有向圖的強(qiáng)連通子圖，也稱做強(qiáng)連通分量，強(qiáng)連通分支和強(qiáng)連通分塊。第五十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義53求強(qiáng)連通子圖的另類算法可以知道，圈上的點(diǎn)都是滿足強(qiáng)連通性質(zhì)的，所以我們可以不斷的找圈，然后壓縮它，直到找不到圈為止。該算法因?yàn)闀r(shí)間復(fù)雜度過(guò)大，本身沒(méi)有什么實(shí)質(zhì)的作用，但是會(huì)給我們的解題思路和算法證明帶來(lái)一定的幫助。第五十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義54求強(qiáng)連通子圖的算法1一種求有向圖強(qiáng)連通子圖的算法和求無(wú)向圖塊的方法幾乎一樣，不同的是，我們需要特殊考慮一下橫叉邊的處理。如果e=u→v是橫叉邊，那么lowlink[u]:=min(lowlink[u],dfn[v])這一步就無(wú)需再做。第五十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義55程序代碼PROCEDUREDFS(v);begin inc(sign);dfn[v]:=sign;//給v按照訪問(wèn)順序的先后標(biāo)號(hào)為sign lowlink[v]:=sign;//給lowlink[v]賦初始值 inc(tot);stack[tot]:=v;//v點(diǎn)進(jìn)棧 instack[v]:=true;//這個(gè)用來(lái)判斷橫叉邊 for尋找一個(gè)v的相鄰節(jié)點(diǎn)u if邊uv沒(méi)有被標(biāo)記過(guò)then begin 標(biāo)記邊uv; 給邊定向v→u; ifu未被標(biāo)記過(guò)then begin DFS(u);//uv是父子邊，遞歸訪問(wèn) lowlink[v]:=min(lowlink[v],lowlink[u]); end第五十五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義56程序代碼 else

ifinstack[u]then lowlink[v]:=min(lowlink[v],dfn[u]);//uv是返祖邊 end; iflowlink[v]=dfn[v]then begin 塊數(shù)目number+1; repeat 標(biāo)記stack[tot]這個(gè)點(diǎn)為number;

instack[stack[tot]]:=false; dec(tot);//點(diǎn)出棧 untilstack[tot+1]=v; end;end;第五十六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義57求強(qiáng)連通子圖的算法2基于兩次DFS的有向圖強(qiáng)連通子圖算法(1)對(duì)圖進(jìn)行DFS遍歷，遍歷中記下所有的dfn[v]的值。遍歷的結(jié)果是構(gòu)造了一座森林W1；(2)改變圖G中的每一條邊的方向，構(gòu)造出新的有向圖Gr；(3)按照dfn[v]由大到小的順序?qū)r進(jìn)行DFS遍歷。遍歷的結(jié)果是構(gòu)造了新的森林W2，W2中的每棵樹(shù)上的頂點(diǎn)構(gòu)成了有向圖的極大強(qiáng)連通子圖。算法證明？第五十七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義58有向圖的壓縮將有向圖中的強(qiáng)連通子圖都?jí)嚎s成為一個(gè)點(diǎn)之后，是否和無(wú)向圖壓縮之后的結(jié)果一樣呢？有向圖壓縮之后，連接不同結(jié)點(diǎn)之間的邊有兩種：父子邊，橫叉邊。壓縮后的圖，不是一個(gè)標(biāo)準(zhǔn)意義上的樹(shù)(將邊看作無(wú)向)。它是一個(gè)無(wú)有向圈的有向圖，即不可再壓縮的圖。有向圖壓縮的意義，在后面的例題《受歡迎的奶牛》中我們會(huì)看到。第五十八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義59探索第二部(1)A和B兩位偵探要合力解決一起謀殺案。現(xiàn)在有N條線索，單獨(dú)的解決一些線索A和B花費(fèi)的時(shí)間是有差別的。而在解決掉某些線索之后，可以毫不費(fèi)力的解決掉另外一些線索。現(xiàn)在你的任務(wù)是求出A和B一起配合解決掉所有線索所需要花費(fèi)的總時(shí)間。數(shù)據(jù)范圍約定：線索數(shù)目N≤1000解決每條線索A和B花費(fèi)的時(shí)間ai和bi都不超過(guò)15第五十九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義60探索第二部(2)如果解決了線索x順邊就能解決線索y，那么在x和y之間連一條有向邊。可知，如果解決了x之后能解決y，解決y之后能解決z，那么說(shuō)明，我們只需要解決掉x，就能解決y和z。一個(gè)顯而易見(jiàn)的性質(zhì)：如果x能通過(guò)有向邊到達(dá)y，y不能通過(guò)有向邊到達(dá)x，那么無(wú)論如何，y都不必解決。第六十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義61探索第二部(3)而如果存在x和y能互達(dá)，那么從中任意挑出一個(gè)來(lái)解決就可以。也就是說(shuō)，在一個(gè)強(qiáng)連通子圖內(nèi)，我們只需要任意挑出一個(gè)線索將它解決，就能解決掉該子圖內(nèi)所有的線索。現(xiàn)在的任務(wù)便成了，挑出所有的必須被解決線索。然后分配A和B去解決他們。這個(gè)問(wèn)題，我們可以用動(dòng)態(tài)規(guī)劃來(lái)解決。第六十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義62探索第二部(4)那么如何處理一個(gè)強(qiáng)連通子圖的情況呢？如果讓A來(lái)解決掉一個(gè)線索，那么肯定挑出A花費(fèi)時(shí)間最少的那條線索；同理如果B來(lái)解決掉一個(gè)線索，那么肯定挑出B花費(fèi)時(shí)間最少的那條線索。于是可以將整個(gè)子圖壓縮成為一個(gè)點(diǎn)，A解決它所需要的時(shí)間是所有點(diǎn)中ai的最小值，B解決它所需要的時(shí)間是所有點(diǎn)中bi的最小值。第六十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義63探索第二部(5)算法流程：(1)根據(jù)輸入建圖(2)求出途中的所有強(qiáng)連通子圖，并壓縮成一個(gè)點(diǎn)(3)挑出森林中所有的根結(jié)點(diǎn)，這些是必須被解決的線索(4)用動(dòng)態(tài)規(guī)劃算法解決最小總花費(fèi)的問(wèn)題第六十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義64受歡迎的奶牛(1)N頭奶牛，給出若干個(gè)歡迎關(guān)系A(chǔ)B，表示A歡迎B，歡迎關(guān)系是單向的，但是是可以傳遞的。另外每個(gè)奶牛都是歡迎他自己的。求出被所有的奶牛歡迎的奶牛的數(shù)目。(USACOFALL03)數(shù)據(jù)范圍約定：奶牛數(shù)目N≤10000直接的歡迎關(guān)系數(shù)目M≤50000第六十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義65受歡迎的奶牛(2)可以想到的是，如果圖中包含有強(qiáng)連通子圖，那么就可以把這個(gè)強(qiáng)連通縮成一個(gè)點(diǎn)，因?yàn)閺?qiáng)連通子圖中的任意兩個(gè)點(diǎn)可以到達(dá)，強(qiáng)連通子圖中所有的點(diǎn)具有相同的性質(zhì)，即它們分別能到達(dá)的點(diǎn)集都是相同的，能夠到達(dá)它們的點(diǎn)集也是相同的。通過(guò)大膽猜想，我們得到一個(gè)結(jié)論：?jiǎn)栴}的解集是壓縮后的圖中，唯一的那個(gè)出度為0的點(diǎn)。第六十五頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義66受歡迎的奶牛(3)首先，如果該圖不是一張連通圖，那么問(wèn)題肯定是無(wú)解的。在假定圖是一張連通圖的情況下，我們需要證明如下一些東西：(1)解集為什么一定構(gòu)成一個(gè)強(qiáng)連通子圖？(2)同時(shí)存在2個(gè)出度為0的獨(dú)立的強(qiáng)連通子圖的時(shí)侯，為什么就一定無(wú)解？(3)只有一個(gè)出度為0的強(qiáng)連通子圖的時(shí)候，為什么該強(qiáng)連通子圖一定是問(wèn)題的解集？(4)如果一個(gè)強(qiáng)連通子圖的出度不為0，為什么就一定不是問(wèn)題的解集？第六十六頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義67受歡迎的奶牛(4)(1)解集為什么一定構(gòu)成一個(gè)強(qiáng)連通子圖？證明：假設(shè)A和B都是最受歡迎的cow，那么，A歡迎B，而且B歡迎A，于是，A和B是屬于同一個(gè)強(qiáng)連通子圖內(nèi)的點(diǎn)，所以，問(wèn)題的解集構(gòu)成一個(gè)強(qiáng)連通子圖。第六十七頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義68受歡迎的奶牛(5)(2)同時(shí)存在2個(gè)出度為0的獨(dú)立的強(qiáng)連通子圖的時(shí)侯，為什么就一定無(wú)解？證明：如果存在兩個(gè)獨(dú)立的強(qiáng)連通分量a和b，那么a內(nèi)的點(diǎn)和b內(nèi)的點(diǎn)一定不能互相到達(dá)，那么，無(wú)論是a還是b都不是解集的那個(gè)連通分量，問(wèn)題保證無(wú)解。第六十八頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義69受歡迎的奶牛(6)(3)只有一個(gè)出度為0的強(qiáng)連通子圖的時(shí)候，為什么該強(qiáng)連通子圖一定是問(wèn)題的解集？證明：假設(shè)在壓縮過(guò)的圖中，存在結(jié)點(diǎn)A，它到出度為0的結(jié)點(diǎn)(設(shè)為Root)沒(méi)有通路，因?yàn)锳的出度一定不為0，那么設(shè)他可以到B，于是B到Root沒(méi)有通路，因?yàn)锽的出度也一定不為0，那么設(shè)他可以到C……，如此繼續(xù)下去，因?yàn)樵搱D已經(jīng)不可再壓縮，所以這樣下去不會(huì)出現(xiàn)已經(jīng)考慮過(guò)的點(diǎn)(否則就存在有向環(huán))，那么這樣下去之后，所有的點(diǎn)都到Root沒(méi)有通路，而Root到其他所有的點(diǎn)也是沒(méi)有通路的，因?yàn)樗某龆葹?，所以Root與其他所有的點(diǎn)是獨(dú)立的，這與大前提“該圖是連通圖”矛盾。所以假設(shè)不成立。第六十九頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義70受歡迎的奶牛(7)(4)如果一個(gè)強(qiáng)連通子圖的出度不為0，為什么就一定不是問(wèn)題的解集？證明：如果某個(gè)強(qiáng)連通子圖內(nèi)的點(diǎn)A到強(qiáng)連通分量外的點(diǎn)B有通路，因?yàn)锽和A不是同一個(gè)強(qiáng)連通子圖內(nèi)的點(diǎn)，所以B到A一定沒(méi)有通路，那么A不被B歡迎，于是A所在的強(qiáng)連通子圖一定不是解集的那個(gè)強(qiáng)連通子圖。第七十頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義71受歡迎的奶牛(8)算法流程：(1)壓縮有向圖(2)判斷連通性，并找到圖中出度為0的點(diǎn)的個(gè)數(shù)。(3)如果圖不連通或者出度為0的點(diǎn)的個(gè)數(shù)超過(guò)1，輸出無(wú)解，否則轉(zhuǎn)(4)(4)輸出出度為0的點(diǎn)代表的強(qiáng)連通子圖上的點(diǎn)第七十一頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義72科學(xué)是在不斷的大膽猜想與小心求證中進(jìn)步的！第七十二頁(yè)，共八十頁(yè)，編輯于2023年，星期二Thankyouforlistening！第七十三頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義74參考文獻(xiàn)王樹(shù)禾《離散數(shù)學(xué)引論》劉汝佳/黃亮《算法藝術(shù)與信息學(xué)競(jìng)賽》吳文虎/王建德《圖論的算法與程序設(shè)計(jì)》第七十四頁(yè)，共八十頁(yè)，編輯于2023年，星期二2023/6/9浙江省2006年集訓(xùn)講義75MST另類算法證明我們通過(guò)kruskal算法的正確性來(lái)證明該算法的正確性設(shè)該算法得到的MST’為T(mén)’，它不是原圖的最小生成樹(shù)T，則存在一條邊e，有e∈T’且e∈T。由于T’不可再調(diào)整，所以在T’中添加e之后，e是所成環(huán)上的最大邊。因而在做kruskal算法時(shí)候，該環(huán)上的所有邊在e之前都會(huì)被事先考慮是否加入MST中，而在