圖論相關(guān)算法

圖論相關(guān)算法圖的組織形式點(diǎn)、邊（有向、無向）、權(quán)（容量、費(fèi)用）矩陣、鄰接表廣度優(yōu)先搜索通常用隊(duì)列(先進(jìn)先出,FIFO)實(shí)現(xiàn)

Q={起點(diǎn)s};標(biāo)記s為己訪問; while(Q非空){

取Q隊(duì)首元素u;u出隊(duì);

所有與u相鄰且未被訪問的點(diǎn)進(jìn)入隊(duì)列;

標(biāo)記u為已訪問; }廣度優(yōu)先搜索由BFS得到的路徑是原圖中從S到T的邊數(shù)最少的路徑廣度優(yōu)先搜索樹不唯一廣度優(yōu)先搜索雙向廣度優(yōu)先搜索適用于已知出發(fā)點(diǎn)和結(jié)束點(diǎn)的BFS減少不必要的狀態(tài)，搜索加速分析：搜索分支因子為r（每次可擴(kuò)展?fàn)顟B(tài)數(shù)），需要k層，總狀態(tài)數(shù)為rk，雙向，前后各rk/2，總狀態(tài)數(shù)2×rk/2哈希判重廣度優(yōu)先搜索無向圖的連通分量無向圖的連通分量是指，在連通分量里面的任意兩個(gè)點(diǎn)之間都有路。易知從某個(gè)點(diǎn)v開始進(jìn)行一次BFS，遍歷到的所有點(diǎn)和v就在同一個(gè)連通分量?jī)?nèi)。廣度優(yōu)先搜索例題：無向單位邊權(quán)值圖，300000個(gè)點(diǎn)，編號(hào)1~n，列出所有中心點(diǎn)的編號(hào)中心點(diǎn)：到圖中其他所有點(diǎn)的最長(zhǎng)距離最小的點(diǎn)廣度優(yōu)先搜索解法：廣搜，遍歷原圖，生成BFS樹求樹的直徑，即樹的最長(zhǎng)路直徑的中間節(jié)點(diǎn)（1個(gè)或者2個(gè)）為中心點(diǎn)廣度優(yōu)先搜索樹的直徑求法：選任意點(diǎn)開始BFS選BFS中深度最大的一個(gè)點(diǎn)為直徑的一個(gè)端點(diǎn)從該端點(diǎn)出發(fā)再BFS最深的節(jié)點(diǎn)為另一端點(diǎn)，且深度為直徑長(zhǎng)度深度優(yōu)先搜索相關(guān)概念遞歸實(shí)現(xiàn)結(jié)點(diǎn)顏色：白色（開始），灰色（發(fā)現(xiàn)），黑色（結(jié)束）一個(gè)結(jié)點(diǎn)總是從白色變?yōu)榛疑僮優(yōu)楹谏?dāng)所有點(diǎn)都變?yōu)楹谏珪r(shí)，遍歷結(jié)束時(shí)間戳(timestamp):d[u]表示一個(gè)結(jié)點(diǎn)開始被訪問的時(shí)間，f[u]表示一個(gè)結(jié)點(diǎn)結(jié)束訪問的時(shí)間深度優(yōu)先搜索inttimestamp=0;dfs(intp){ timestamp=timestamp+1;

col[p]=GREY;

d[p]=timestamp; for(每個(gè)與p相鄰的點(diǎn)i) if(col[i]==WHITE)dfs(i); timestamp=timestamp+1;

f[p]=timestamp;

col[p]=BLACK;}深度優(yōu)先搜索每個(gè)頂點(diǎn)的d[u]<f[u]DFS中，v是u的子孫

d[u]<d[v]<f[v]<f[u]在搜索中發(fā)現(xiàn)u時(shí)可以從u出發(fā)沿一條完全由白色頂點(diǎn)組成的路徑到達(dá)vm條邊的連通圖，DFS中順序標(biāo)號(hào)每條邊為1~m，則任意與頂點(diǎn)u關(guān)聯(lián)的所有邊（邊數(shù)>=2）的標(biāo)號(hào)的GCD為1深度優(yōu)先搜索割點(diǎn)與割邊如果從圖中刪去某點(diǎn)和與該點(diǎn)相關(guān)聯(lián)的邊后，圖不再連通，那么這個(gè)點(diǎn)叫做割點(diǎn)(cutpoint)。如果從圖中刪去某條邊后，圖不再連通，那么這條邊叫做割邊或橋(bridge)。深度優(yōu)先搜索思路dep[u]記錄節(jié)點(diǎn)u在DFS樹中的深度low[u]記錄節(jié)點(diǎn)u的子孫所能達(dá)到的最淺深度u為割點(diǎn)

u為根，且有大于1個(gè)兒子u不為根，且u的某個(gè)兒子v有l(wèi)ow[v]>=dep[u](u,v)為割邊

點(diǎn)u的某個(gè)兒子v，有l(wèi)ow[v]>dep[u]深度優(yōu)先搜索dfs(int

k,intfather,intdepth){

col[k]=GREY;dep[k]=depth;tot=0; for(每個(gè)與k相鄰的點(diǎn)i){ if(i!=father&&col[i]==GREY)

low[k]=min(low[k],dep[i]); if(col[i]==WHITE){

dfs(i,k,depth+1); tot=tot+1;

low[k]=min(low[k],low[i]); if((k為根&&tot>1)||(k不為根&&low[i]>=dep[k])) k為割點(diǎn); if(low[i]>dep[k])then(k,i)為割邊; } }

col[k]=BLACK;}深度優(yōu)先搜索例題：某公司擁有N臺(tái)計(jì)算機(jī)，并將他們組成局域網(wǎng)，現(xiàn)在要求尋找該局域網(wǎng)中的關(guān)鍵點(diǎn)（即割點(diǎn)），并求出一旦處于該關(guān)鍵點(diǎn)的計(jì)算機(jī)崩潰，原局域網(wǎng)將會(huì)分成多少個(gè)子網(wǎng)深度優(yōu)先搜索SampleInput125431323435012233445510122334466325510深度優(yōu)先搜索SampleOutputNetwork#1:SPFnode3leaves2subnetsNetwork#2:NoSPFnodesNetwork#3:SPFnode2leaves2subnetsSPFnode3leaves2subnets深度優(yōu)先搜索解法：求割點(diǎn)，計(jì)算刪除該點(diǎn)使連通分量增加數(shù)對(duì)于DFS森林，對(duì)每個(gè)割點(diǎn)記錄一個(gè)cnt值，若有一個(gè)兒子v使得low[v]>=dep[u]則使cnt[u]++，則有如下性質(zhì)： 對(duì)每個(gè)非根割點(diǎn)，刪除該節(jié)點(diǎn)會(huì)增加cnt[u]個(gè)連通分量對(duì)每個(gè)根割點(diǎn)，刪除該點(diǎn)會(huì)使圖的連通分量增加其兒子數(shù)-1個(gè)拓?fù)渑判驁D的結(jié)點(diǎn)存在一個(gè)拓?fù)湫颍喝绻麍D中有邊(u，v)，則u必定排在v的前面拓?fù)渑判蛟谟邢驘o環(huán)圖(DAG)上進(jìn)行拓?fù)湫蛄胁灰欢ㄎㄒ煌負(fù)渑判蚶肈FS，當(dāng)節(jié)點(diǎn)u已經(jīng)擴(kuò)展完成，將標(biāo)記顏色置為黑時(shí)，將u加入已排序列的頂部，搜索完成時(shí)，節(jié)點(diǎn)序列為拓?fù)湫蚪?jīng)過拓?fù)渑判虻捻旤c(diǎn)以與其完成時(shí)刻相反的順序出現(xiàn)拓?fù)渑判蛩惴?1)計(jì)算每個(gè)點(diǎn)的入度，入度為0的點(diǎn)加入隊(duì)列Q(2)從Q中取出一個(gè)點(diǎn)p，輸出(3)所有與p相鄰的點(diǎn)的入度減1。如果新得到了入度為0的點(diǎn)，則加入隊(duì)列Q。(4)轉(zhuǎn)步驟(2),直到所有點(diǎn)都輸出完畢如果在執(zhí)行過程中發(fā)現(xiàn)找不到入度為0的點(diǎn),說明圖中存在環(huán)拓?fù)渑判?3245678(不唯一)如何生成最小字典序的拓?fù)湫蛄?？可以使用最小堆維護(hù)當(dāng)前入度為0的節(jié)點(diǎn)21348756強(qiáng)連通分量有向圖的強(qiáng)連通分量（SCC）指：對(duì)于強(qiáng)連通分量里面的任意兩個(gè)節(jié)點(diǎn)u和v，都存在u到v和v到u的路強(qiáng)連通分量思路：對(duì)原圖G進(jìn)行DFS，記錄各點(diǎn)的結(jié)束時(shí)間，把原圖G的所有邊反向?yàn)镚T，在GT以各點(diǎn)結(jié)束時(shí)間遞減的順序DFS，則每棵樹都是一個(gè)強(qiáng)連通分量即第一遍DFS生成拓?fù)湫颍酝負(fù)湫蜃龅诙蜠FS強(qiáng)連通分量縮點(diǎn)操作生成一個(gè)新的有向圖Gscc，將每個(gè)強(qiáng)連通分量作為新圖的一個(gè)點(diǎn)，原圖連通分量?jī)?nèi)部的邊刪除，連通分量之間的邊保留新圖必定有拓?fù)湫颍床粫?huì)出現(xiàn)有向環(huán)(DAG)Gscc稱為原圖的核心DAG強(qiáng)連通分量強(qiáng)連通分量例題：隊(duì)長(zhǎng)要向所有人通知某件事情，因?yàn)槿藬?shù)眾多，他想出了一個(gè)省力的方法：他只通知隊(duì)中的某些人，然后讓這些人去通知所有他們認(rèn)識(shí)的人，這些新被通知的人又去通知更多的人……直到最后隊(duì)中的所有人都被通知到。給定隊(duì)長(zhǎng)通知每個(gè)人所需的花費(fèi)，現(xiàn)在他想求出一種方案，使得花費(fèi)最少，并且保證最終所有人都能被通知到。強(qiáng)連通分量SampleInput4330201040122123SampleOutput60強(qiáng)連通分量解題：同一個(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)解強(qiáng)連通分量例題：給一個(gè)有向圖G，添加最少的邊數(shù)使得G中各點(diǎn)能兩兩互通（即每對(duì)點(diǎn)a和b，a能到b，b也能到a），求最少的邊數(shù)強(qiáng)連通分量解題：對(duì)原圖求強(qiáng)連通分量，形成新的DAG圖Gscc對(duì)Gscc計(jì)算入度為0的點(diǎn)的個(gè)數(shù)為x對(duì)Gscc計(jì)算出度為0的點(diǎn)的個(gè)數(shù)為y答案為max(x,y)，即從出度為0的點(diǎn)向入度為0的點(diǎn)連max(x,y)條邊歐拉路歐拉路：經(jīng)過圖中每條邊恰好一次的路歐拉回路：起點(diǎn)和終點(diǎn)相同的歐拉路歐拉路無向圖存在歐拉路的條件如果圖連通，且所有的點(diǎn)都是偶數(shù)度，則有歐拉回路。如果圖連通，且恰有兩點(diǎn)是奇數(shù)度，則有歐拉路。且歐拉路的起止點(diǎn)為這兩個(gè)奇數(shù)度點(diǎn)。對(duì)重邊、自環(huán)的情況仍適用。歐拉路有向圖存在歐拉路的條件如果圖連通，且每個(gè)點(diǎn)的入度等于出度，則存在歐拉回路。如果圖連通，且恰有一點(diǎn)u的出度比入度大1，另有一點(diǎn)v的出度比入度小1，其余的出度等于出度，則存在歐拉路，起點(diǎn)為u，終點(diǎn)為v。對(duì)重邊、自環(huán)的情況仍適用。歐拉路套圈算法voidEuler(intstart){ for(inti=1;i<=E;i++){ if(!visit[i]&&from==start){

visit[i]=1;

Euler(to); path[++top]=i; } }}倒序path[]為歐拉路歐拉路例題：給定一組單詞，問這些單詞能否連成一串，使得前面一個(gè)單詞的最后一個(gè)字母和后面一個(gè)單詞的第一個(gè)字母相同。歐拉路SampleInput 6 aloha arachnid dog gopher rat tiger 3 oak maple elmSampleOutputaloha.arachnid.dog.gopher.rat.tiger

***歐拉路解法：先判斷連通性每個(gè)單詞相當(dāng)于在首字母和尾字母之間連一條邊得到一個(gè)最多26個(gè)點(diǎn)的有向圖求歐拉路漢密爾頓路漢密爾頓路：經(jīng)過圖中每個(gè)點(diǎn)恰好一次的路漢密爾頓回路：起點(diǎn)和終點(diǎn)相同的漢密爾頓路常見方法：狀態(tài)壓縮DP漢密爾頓路對(duì)于點(diǎn)數(shù)較少的情況，可以用狀態(tài)壓縮的DP來做。比如用opt[mask][k]表示已經(jīng)訪問過mask表示的結(jié)點(diǎn)集合，并且最后位于點(diǎn)k的最優(yōu)解。狀態(tài)轉(zhuǎn)移方程為：opt[mask][k]=min(opt[mask-{k}][i]+cost[i][k])i是所有與k相鄰的點(diǎn)，mask-{k}指從mask除去k最短路徑單源最短路徑DijkstraBellman-FordSPFA任意兩點(diǎn)間Floyd最短路徑復(fù)雜度：Dijkstra:O(V2)或O(E+VlgV)Bellman-Ford:O(EV)Floyd:O(V3)SPFA:期望復(fù)雜度O(E)最短路徑算法選擇：編程復(fù)雜度：Bellman-Ford<Floyd<Dijkstra時(shí)間復(fù)雜度：Dijkstra<Bellman-Ford使用范圍：有負(fù)權(quán)邊需要使用Bellman-Ford如果是稀疏圖，即使是求任意兩點(diǎn)間最短路徑，也最好選用堆優(yōu)化的Dijkstra最短路徑單源最短路徑的核心松弛操作If(d[j]>d[i]+cost[i][j])d[j]=d[i]+cost[i][j];最短路徑Dijkstra最短路徑Bellman-Ford主體思想：對(duì)圖中每條邊做|V|-1次松弛操作，即可確定最短路徑，當(dāng)有負(fù)權(quán)值時(shí)，再對(duì)所有邊做一次松弛操作，若dis值仍有變化則表明存在負(fù)環(huán)最短路徑bool

Bellman(intn,intm){ /*bellman,returnfalsewhenthereisanagetivecircle*/

intu,v,w,i,j;

boolflag;

for(i=1;i<=n;i++){ flag=0;

for(j=0;j<m;j++){ u=edge[j].from,v=edge[j].to,w=edge[j].value;

if(dis[v]>dis[u]+w){

dis[v]=dis[u]+w; flag=1; } }

if(!flag)break;

if(i==n&&flag)returnfalse; } returntrue;}最短路徑SPFA作為一種動(dòng)態(tài)逼近的方法，是一種迭代模式，不僅僅可以用在最短路中，可以解決帶環(huán)的DP問題最短路徑

Q={s};d[s]=0; while(Q非空){

取隊(duì)首元素u;u出隊(duì); for(與u相鄰的點(diǎn)v){ if(d[v]>d[u]+cost[u][v]){

d[v]=d[u]+cost[u][v]; if(v不在隊(duì)中)thenv入隊(duì); }//若某個(gè)點(diǎn)入隊(duì)次數(shù)達(dá)到|v|說明有負(fù)環(huán)

} }可以用循環(huán)隊(duì)列實(shí)現(xiàn)，隊(duì)列中元素個(gè)數(shù)不超過|V|最短路徑例題：最小平均環(huán)路圖的每條邊有兩個(gè)權(quán)值a和b，在圖上找一個(gè)環(huán)，使得對(duì)于環(huán)上的所有邊（∑a/∑b）最小最短路徑解法：二分答案設(shè)答案為k，使各邊的邊權(quán)值為k×b[i]–a[i]，在新圖中用Bellman-Ford或者SPFA判斷是否含有負(fù)環(huán)若有負(fù)環(huán)，則k×b[i]–a[i]<0即k<∑a/∑b，即可再擴(kuò)大k最短路徑例題：有向圖，N個(gè)節(jié)點(diǎn)編號(hào)1~N，M條邊，權(quán)值均為正，現(xiàn)給定k個(gè)可替換條件，可以將M條件中的k條邊權(quán)值替換為0，求在至多替換k條邊的情況下，節(jié)點(diǎn)1到節(jié)點(diǎn)N的最短路徑最短路徑解法：多層圖建立一個(gè)多層圖，有k+1層，每層都為原圖，只有相鄰層之間可建邊，且相鄰層間只能建立由低層到高層的邊，若圖中有邊（i，j）權(quán)值為p，則建立下層節(jié)點(diǎn)i到上層節(jié)點(diǎn)j的權(quán)值為0的邊第0層（最下一層）節(jié)點(diǎn)1到第k層（最上一層）節(jié)點(diǎn)N的最短路徑為所求差分約束差分約束系統(tǒng)是一組形如x-y<=C的不等式

x1–x2<=0 x1–x5<=-1 x2–x5<=1 x3–x1<=5 x4–x1<=4 x4–x3<=-1 x5–x3<=-3 x5–x4<=-3差分約束松馳操作if(d[v]>d[u]+cost) thend[v]=d[u]+cost;在最短路算法執(zhí)行完畢后，對(duì)所有的邊(u,v)都有

d[v]<=d[u]+cost

變形得

d[v]–d[u]<=cost;容易看出，上式即為差分約束系統(tǒng)的標(biāo)準(zhǔn)形式。差分約束解不等式組問題轉(zhuǎn)化為圖論問題：不等式組中的每個(gè)變量作為圖中的一個(gè)點(diǎn)對(duì)于每個(gè)不等式Xi–Xj<=k，在圖中加入一條邊(j,i)，邊權(quán)值為k為了執(zhí)行最短路算法，我們加入一個(gè)源點(diǎn)V0，并使V0到每個(gè)點(diǎn)有一條權(quán)值為0的邊。以V0為起點(diǎn)，執(zhí)行Bellman-Ford算法，算法結(jié)束時(shí)各個(gè)點(diǎn)的d[]值即為一個(gè)可行解。如果算法檢測(cè)到負(fù)環(huán)，說明原不等式組無解差分約束若題目中為>，<可以通過+1，-1來轉(zhuǎn)變成為>=，=<當(dāng)某些點(diǎn)有明顯的<=性質(zhì)時(shí)，可以計(jì)算和值，使得Si–Si-1產(chǎn)生<=形式，構(gòu)造求解實(shí)際問題中有些不等關(guān)系較隱蔽，注意不要遺漏如果把所有的Xi同時(shí)加一個(gè)值，不等式組仍然成立生成樹最小生成樹：Prim(O(ElogV))Kruskal(O(ElogE)+O(alpha*E))算法的選擇：從圖的稀疏程度考慮從問題對(duì)邊的限制考慮最小生成樹Prim算法：(1)任意選定一點(diǎn)s，設(shè)集合S={s}(2)從不在集合S的點(diǎn)中選出一個(gè)點(diǎn)j使得其與S內(nèi)的某點(diǎn)i的距離最短，則(i，j)就是生成樹上的一條邊，同時(shí)將j點(diǎn)加入S(3)轉(zhuǎn)到(2)繼續(xù)進(jìn)行，直至所有點(diǎn)都己加入S集合。最小生成樹50461321025142422161850461210251422161231228最小生成樹Kruskal算法：將邊按權(quán)值從小到大排序后逐個(gè)判斷，如果當(dāng)前的邊加入以后不會(huì)產(chǎn)生環(huán)，那么就把當(dāng)前邊作為生成樹的一條邊。最終得到的結(jié)果就是最小生成樹。并查集最小生成樹50461321025142416181250461321025141222222816生成樹其他生成樹問題：最小樹形圖有向圖的最小生成樹次小生成樹假設(shè)T為G的最小生成樹集合，并設(shè)T’為T的最小生成樹，那么次小生成樹是集合T’-T中權(quán)值最小的生成樹生成樹其他生成樹問題：最小度限制生成樹對(duì)于一個(gè)加權(quán)的無向圖，存在一些滿足下面性質(zhì)的生成樹：某個(gè)特殊的結(jié)點(diǎn)的度等于一個(gè)指定的數(shù)值。最小度限制生成樹就是滿足此性質(zhì)且權(quán)值和最小的一棵生成樹最優(yōu)比率生成樹已知一個(gè)完全圖，每條邊有兩個(gè)參數(shù)（dis和c），求一棵生成樹，使(∑xi×ci)/(∑xi×disi)最小，其中xi當(dāng)?shù)趇條邊包含在生成樹中時(shí)為1，否則為0二分圖所有點(diǎn)可以分成兩個(gè)集合X和Y，使得所有的邊的一端在X集合，另一端在Y集合二分圖的充要條件：圖中不含奇環(huán)二分圖的判定：用BFS或DFS對(duì)點(diǎn)進(jìn)行黑白染色，檢查是否出現(xiàn)矛盾二分圖最大匹配二分圖的最大匹配指找到盡可能多的邊，使得它們之間沒有相同的端點(diǎn)二分圖最大匹配交錯(cuò)路對(duì)于一個(gè)匹配M，如果能找到一條奇數(shù)長(zhǎng)度的路，使得路的第一、三、五……邊不屬于M，而第二、四、六……邊屬于M，那么這條路叫做交錯(cuò)路。交錯(cuò)路可以“增廣”，即通過適當(dāng)修改得到更長(zhǎng)的路。一個(gè)匹配是最大匹配當(dāng)且僅當(dāng)不能再找到交錯(cuò)鏈為止二分圖最大匹配交錯(cuò)路增廣示例(1-2-3-4-5-6-7-8)12345678二分圖最大匹配匈牙利算法一個(gè)匹配為最大匹配

匹配中不存在交錯(cuò)路利用BFS或者DFS實(shí)現(xiàn)尋找交錯(cuò)路以每個(gè)節(jié)點(diǎn)為起點(diǎn)找一次增廣路即可求得最大匹配，尋找增廣路的復(fù)雜度為O（E），總的復(fù)雜度為O（VE）二分圖最大匹配bool

Bipartite_Dfs(intu){

for(inti=0;i<adj[u].size();i++){

if(!mark[adj[u][i]]){

mark[adj[u][i]]=1;

intt=match[adj[u][i]];

match[adj[u][i]]=u;

if(!t||Bipartite_Dfs(t))returntrue;

match[adj[u][i]]=t; } } returnfalse;}------------------------------------------------------------------------------------------------Clear(match);for(i=1;i<=n;i++){

Clear(mark);

if(Bipartite_Dfs(i))ans++;}二分圖最大匹配可以在調(diào)用DFS增廣之前利用貪心的策略做初始的基本匹配，若貪心解接近最終解則可提高效率常見模型：非攻擊車：行列分為兩部分，允許放車的格子連邊骨牌覆蓋：染色，相鄰黑白格連邊二分圖最大匹配例題：給一個(gè)N×M的格子，其中‘X’表示不能走，‘E’表示出口，‘.’表示有一個(gè)人。所有人只能上下左右行走，且所有人都要選擇一個(gè)出口走出去，但每個(gè)時(shí)刻每個(gè)出口只能走出去一個(gè)人，問是否所有人都能出去，如果是，求都能出去的最小時(shí)間二分圖最大匹配解答：二分答案+最大匹配驗(yàn)證從每個(gè)‘E’出口BFS遍歷每個(gè)‘.’人，計(jì)算編號(hào)為i的人到編號(hào)為j的出口的最短距離（也是最短時(shí)間），記錄于cnt[i][j]二分最后時(shí)間k，將原總共d個(gè)出口拆成k×d個(gè)出口，若cnt[i][j]<=k，則i可以連邊指向編號(hào)為j的出口拆成時(shí)間從cnt[i][j]到k的點(diǎn)二分圖最大匹配解答：求二分圖最大匹配若匹配值==總?cè)藬?shù)，right=mid–1否則，left=mid+1另外需要注意本身無法到達(dá)出口的情況二分圖最小點(diǎn)覆蓋點(diǎn)覆蓋：求出一個(gè)點(diǎn)集，使得圖中的所有邊都至少有一個(gè)端點(diǎn)在該點(diǎn)集內(nèi)。最小點(diǎn)覆蓋：節(jié)點(diǎn)數(shù)最少的點(diǎn)覆蓋二分圖的最小點(diǎn)覆蓋=二分圖的最大匹配二分圖最小點(diǎn)覆蓋構(gòu)造最小點(diǎn)覆蓋求得最大匹配M后，圖中已經(jīng)不存在交錯(cuò)路。從右邊未匹配的點(diǎn)開始，以尋找交錯(cuò)路的方式擴(kuò)展節(jié)點(diǎn)，并標(biāo)記路過的節(jié)點(diǎn)。取右邊未標(biāo)記的節(jié)點(diǎn)，左邊標(biāo)記的節(jié)點(diǎn)，則構(gòu)成一組最小覆蓋二分圖最小點(diǎn)覆蓋二分圖最小點(diǎn)覆蓋例題：有兩臺(tái)機(jī)器A，B及N個(gè)任務(wù)。每臺(tái)機(jī)器有M種不同的模式，對(duì)每個(gè)任務(wù)i給定a[i]和b[i]，表示如果該任務(wù)在A上執(zhí)行，需要設(shè)置模式為a[i]，如果在B上執(zhí)行，需要模式為b[i]。任務(wù)可以以任意順序被執(zhí)行，但每臺(tái)機(jī)器轉(zhuǎn)換一次模式就要重啟一次要求合理分配任務(wù)并合理安排順序，使得機(jī)器重啟次數(shù)最少二分圖最小點(diǎn)覆蓋SampleInput5510011112213314421522623724833943SampleOutput3二分圖最小點(diǎn)覆蓋解法：把兩臺(tái)機(jī)器的工作模式看成頂點(diǎn)，如果一個(gè)工作在第一臺(tái)機(jī)器上用模式i完成，在第二臺(tái)機(jī)器上用模式j(luò)完成，那么就用一條邊把這兩個(gè)頂點(diǎn)連接起來，這樣對(duì)于所有的邊，他們都有一個(gè)頂點(diǎn)是機(jī)器1的工作模式，另一頂點(diǎn)是機(jī)器2的工作模式，于是構(gòu)成的圖是個(gè)二分圖。用最少的模式完成所有的工作，就相當(dāng)于在圖中用最少的點(diǎn)覆蓋所有的邊二分圖最大獨(dú)立集獨(dú)立集：圖的頂點(diǎn)集的子集，其中任意兩個(gè)點(diǎn)在圖中不相鄰最大獨(dú)立集：節(jié)點(diǎn)數(shù)最多的獨(dú)立集二分圖的最大獨(dú)立集=頂點(diǎn)數(shù)–最大匹配數(shù)二分圖最大獨(dú)立集黑色節(jié)點(diǎn)為最大獨(dú)立集二分圖最大獨(dú)立集理解：方式1：在總的點(diǎn)集中，去掉最少的點(diǎn)，使得剩下的點(diǎn)相互之間沒有邊，而用最少的點(diǎn)去覆蓋所有的邊就是最小點(diǎn)覆蓋二分圖的最大獨(dú)立集=圖的點(diǎn)數(shù)-最小點(diǎn)覆蓋數(shù)方式2：在總的點(diǎn)集中，把最大匹配的兩個(gè)端點(diǎn)都去掉，則剩余點(diǎn)構(gòu)成一個(gè)獨(dú)立集，再取最大匹配邊的一個(gè)端點(diǎn)加入，仍為獨(dú)立集二分圖的最大獨(dú)立集=圖的點(diǎn)數(shù)-最大匹配數(shù)二分圖最大獨(dú)立集例題：學(xué)校里有一些男生和女生，其中某些人之間是戀愛關(guān)系?，F(xiàn)在要求找出一個(gè)最大的集合，使得里面的任意兩個(gè)人都沒有關(guān)系二分圖最大獨(dú)立集SampleInput170:(3)4561:(2)462:(0)3:(0)4:(2)015:(1)06:(2)01SampleOutput15

SampleInput230:(2)121:(1)02:(1)0SampleOutput22二分圖最大獨(dú)立集解法：輸入數(shù)據(jù)里面沒有指明性別。必須先進(jìn)行染色，區(qū)分出X集和Y集求二分圖最大獨(dú)立集二分圖最小路徑覆蓋最小路徑覆蓋：用最少的不相交路徑覆蓋有向無環(huán)圖的所有頂點(diǎn)把原圖中的每個(gè)點(diǎn)i拆為兩個(gè)，分別屬于X集和Y集。對(duì)于原圖中的有向邊(i，j)，在新圖中添加邊(Xi，Yj)最小路徑覆蓋數(shù)=原圖頂點(diǎn)數(shù)–新圖最大匹配數(shù)二分圖最小路徑覆蓋解釋：原圖的路徑覆蓋和新圖的匹配間有對(duì)應(yīng)關(guān)系：每條覆蓋邊都是匹配中的一條邊，且只有路徑的最后一個(gè)點(diǎn)沒有被匹配上。路徑要求不能相交，恰好對(duì)應(yīng)于匹配中兩匹配邊不能有公共端點(diǎn)。二分圖最小路徑覆蓋解釋：于是求最大匹配后，不能被匹配上的點(diǎn)，即是路徑的最后一個(gè)點(diǎn)。有多少個(gè)不能被匹配的點(diǎn)，就有多少條路徑存在。路徑數(shù)=原點(diǎn)數(shù)－匹配邊數(shù)。因此我們使匹配邊數(shù)最大，即是使路徑數(shù)最小。二分圖最小路徑覆蓋例題：某汽車運(yùn)輸公司需要安排他們的運(yùn)送線路，已知從某地點(diǎn)X，坐標(biāo)為（a，b），到某地點(diǎn)Y，坐標(biāo)為（c，d）需要的時(shí)間為|a-c|+|b-d|分鐘，現(xiàn)給出所有運(yùn)送安排，求使用最少的車來完成該運(yùn)送安排二分圖最小路徑覆蓋SampleInput2208:00101191608:079161011208:00101191608:069161011SampleOutput12二分圖最小路徑覆蓋解法：每條計(jì)劃作為一個(gè)節(jié)點(diǎn)，令car[i].start=t1*60+t2;car[i].end=car[i].start+|car[i].a-car[i].c|+|car[i].b-car[i].d|;

建邊若car[j].start-car[i].end>|car[i].c-car[j].a|+|car[i].d-car[j].b|則建立i到j(luò)的邊答案=頂點(diǎn)數(shù)–最大匹配數(shù)二分圖最優(yōu)匹配二分圖最優(yōu)匹配（帶權(quán)最大匹配）：二分圖的每條邊上帶有權(quán)值，求一個(gè)匹配使得匹配邊上的權(quán)值和最大。實(shí)際問題：每個(gè)工人操作不同機(jī)器的效率不同，如何合理分配機(jī)器，使得效率總和達(dá)到最佳？每對(duì)男女之間的好感度不同，如何配對(duì)使得總的好感度最高？二分圖最優(yōu)匹配KM算法：基本概念：可行頂標(biāo)與相等子圖可行頂標(biāo)是一個(gè)關(guān)于節(jié)點(diǎn)的函數(shù)L且對(duì)于每條邊(x，y)滿足L(x)+L(y)>=w(x,y)相等子圖是指只包含L(x)+L(y)=w(x,y)的邊的子圖。定理：如果相等子圖有完備匹配（包含所有點(diǎn)的匹配），則該匹配是最大權(quán)匹配。二分圖最優(yōu)匹配KM算法的關(guān)鍵：通過適當(dāng)?shù)匦薷目尚许敇?biāo)從而使相等子圖有完備匹配，于是就可以得到最優(yōu)匹配。設(shè)頂點(diǎn)Xi的頂標(biāo)為a[i]，頂點(diǎn)Yi的頂標(biāo)為b[i]。初始時(shí)，a[i]為與Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立。二分圖最優(yōu)匹配若相等子圖中不包含完備匹配時(shí)，就適當(dāng)修改頂標(biāo)以擴(kuò)大相等子圖，直到找到完備匹配為止當(dāng)從Xi尋找交錯(cuò)路失敗后，得到一棵交錯(cuò)樹，它的所有葉子節(jié)點(diǎn)都是X節(jié)點(diǎn)，取所有左側(cè)點(diǎn)i在樹中而右側(cè)j不在樹中的邊(i,j)，計(jì)算d=min{a[i]+b[j]-w[i][j]}。交錯(cuò)樹中所有左側(cè)點(diǎn)頂標(biāo)-d，右側(cè)點(diǎn)頂標(biāo)+d…二分圖最優(yōu)匹配對(duì)于圖中所有的邊(i,j)，可以看到若i和j都不在交錯(cuò)樹中，邊(i,j)仍不屬于相等子圖若i和j都在交錯(cuò)樹中，邊(i,j)仍然屬于相等子圖若i在交錯(cuò)樹中，j不在交錯(cuò)樹中，a[i]+b[j]減少，邊(i,j)有可能加入到相等子圖中每次更新頂標(biāo)，至少有一條邊新加入相等子圖，匹配也就可能繼續(xù)擴(kuò)大二分圖最優(yōu)匹配例題：在一片花園中，有人（’H’），有屋（’m’），有空地（’.’），且人和屋子的數(shù)量一致，每個(gè)屋子只能住一個(gè)人，每個(gè)人只能上下左右四個(gè)方向行走，現(xiàn)在給你花園的現(xiàn)狀，求使每個(gè)人都能進(jìn)到屋子里的最小步數(shù)二分圖最優(yōu)匹配SampleInput

55HH..m...............mm..H78...H.......H.......H....mmmHmmmm...H.......H.......H....SampleOutput

1028二分圖最優(yōu)匹配解法：初始算出每個(gè)人到每個(gè)房子所需要的步數(shù)，X集為N個(gè)人，Y集為N個(gè)房子，若人i到房子j需要步數(shù)為c，則人i和房子j之間連邊，權(quán)值為-c由于房子數(shù)和人數(shù)一致，可以使用KM算法求解求出的結(jié)果值再取負(fù)即為答案二分圖最優(yōu)匹配注意在使用KM算法時(shí)需要注意X集和Y集的節(jié)點(diǎn)數(shù)是否一致，否則需要補(bǔ)點(diǎn)補(bǔ)邊算最大值時(shí)可以令邊權(quán)為正，反之算最小值時(shí)可以令邊權(quán)為負(fù)，最后結(jié)果再取負(fù)網(wǎng)絡(luò)流網(wǎng)絡(luò)流基本概念：源點(diǎn)(source,常記為s)匯點(diǎn)(sink,常記為t)容量(capacity,常用c(x,y)表示)流(flow,常用f(x,y)表示)網(wǎng)絡(luò)流容量限制條件：對(duì)于所有邊，有f(x,y)<=c(x,y)流量平衡條件：對(duì)于所有非s和t的點(diǎn)u，有∑v∈Vf(u,v)=0網(wǎng)絡(luò)流問題：在滿足上述兩個(gè)限制條件的基礎(chǔ)上，找到合適的f值，使得∑v∈Vf(s,v)最大易得∑v∈Vf(s,v)=∑v∈Vf(v,t)=網(wǎng)絡(luò)流值F網(wǎng)絡(luò)流網(wǎng)絡(luò)流增廣路算法涉及概念：容量：“不存在”的邊容量為0流量：f(u,v)=-f(v,u)殘量網(wǎng)絡(luò)(residualnetworks)R(u,v)=c(u,v)–f(u,v)容量必為正，殘量網(wǎng)絡(luò)必為正，流量可正可負(fù)網(wǎng)絡(luò)流可增廣路(augmentingpath)：在殘量網(wǎng)絡(luò)中的一條s-t路我們可以沿著可增廣路進(jìn)行增廣，從而擴(kuò)大流量，而不破壞限制條件。當(dāng)不能再找到可增廣路時(shí)，我們就得到了一個(gè)網(wǎng)絡(luò)流。網(wǎng)絡(luò)流注意：負(fù)流量的意義R(x,y)=c(x,y)–f(x,y)如果從y到x的流量為正，則從x到y(tǒng)的流量為負(fù)。負(fù)流量對(duì)應(yīng)反向的正的殘量邊，意味著我們可以把這個(gè)流“退回”一部分。網(wǎng)絡(luò)