圖論相關(guān)算法

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

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

取Q隊首元素u;u出隊;

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

標(biāo)記u為已訪問; }廣度優(yōu)先搜索由BFS得到的路徑是原圖中從S到T的邊數(shù)最少的路徑廣度優(yōu)先搜索樹不唯一廣度優(yōu)先搜索雙向廣度優(yōu)先搜索適用于已知出發(fā)點和結(jié)束點的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)先搜索無向圖的連通分量無向圖的連通分量是指，在連通分量里面的任意兩個點之間都有路。易知從某個點v開始進(jìn)行一次BFS，遍歷到的所有點和v就在同一個連通分量內(nèi)。廣度優(yōu)先搜索例題：無向單位邊權(quán)值圖，300000個點，編號1~n，列出所有中心點的編號中心點：到圖中其他所有點的最長距離最小的點廣度優(yōu)先搜索解法：廣搜，遍歷原圖，生成BFS樹求樹的直徑，即樹的最長路直徑的中間節(jié)點（1個或者2個）為中心點廣度優(yōu)先搜索樹的直徑求法：選任意點開始BFS選BFS中深度最大的一個點為直徑的一個端點從該端點出發(fā)再BFS最深的節(jié)點為另一端點，且深度為直徑長度深度優(yōu)先搜索相關(guān)概念遞歸實現(xiàn)結(jié)點顏色：白色（開始），灰色（發(fā)現(xiàn)），黑色（結(jié)束）一個結(jié)點總是從白色變?yōu)榛疑僮優(yōu)楹谏?dāng)所有點都變?yōu)楹谏珪r，遍歷結(jié)束時間戳(timestamp):d[u]表示一個結(jié)點開始被訪問的時間，f[u]表示一個結(jié)點結(jié)束訪問的時間深度優(yōu)先搜索inttimestamp=0;dfs(intp){ timestamp=timestamp+1;

col[p]=GREY;

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

f[p]=timestamp;

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

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

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

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

k,intfather,intdepth){

col[k]=GREY;dep[k]=depth;tot=0; for(每個與k相鄰的點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為割點; if(low[i]>dep[k])then(k,i)為割邊; } }

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

visit[i]=1;

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

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

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

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

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

} }可以用循環(huán)隊列實現(xiàn)，隊列中元素個數(shù)不超過|V|最短路徑例題：最小平均環(huán)路圖的每條邊有兩個權(quán)值a和b，在圖上找一個環(huán)，使得對于環(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個節(jié)點編號1~N，M條邊，權(quán)值均為正，現(xiàn)給定k個可替換條件，可以將M條件中的k條邊權(quán)值替換為0，求在至多替換k條邊的情況下，節(jié)點1到節(jié)點N的最短路徑最短路徑解法：多層圖建立一個多層圖，有k+1層，每層都為原圖，只有相鄰層之間可建邊，且相鄰層間只能建立由低層到高層的邊，若圖中有邊（i，j）權(quán)值為p，則建立下層節(jié)點i到上層節(jié)點j的權(quán)值為0的邊第0層（最下一層）節(jié)點1到第k層（最上一層）節(jié)點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í)行完畢后，對所有的邊(u,v)都有

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

變形得

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

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

SampleInput230:(2)121:(1)02:(1)0SampleOutput22二分圖最大獨立集解法：輸入數(shù)據(jù)里面沒有指明性別。必須先進(jìn)行染色，區(qū)分出X集和Y集求二分圖最大獨立集二分圖最小路徑覆蓋最小路徑覆蓋：用最少的不相交路徑覆蓋有向無環(huán)圖的所有頂點把原圖中的每個點i拆為兩個，分別屬于X集和Y集。對于原圖中的有向邊(i，j)，在新圖中添加邊(Xi，Yj)最小路徑覆蓋數(shù)=原圖頂點數(shù)–新圖最大匹配數(shù)二分圖最小路徑覆蓋解釋：原圖的路徑覆蓋和新圖的匹配間有對應(yīng)關(guān)系：每條覆蓋邊都是匹配中的一條邊，且只有路徑的最后一個點沒有被匹配上。路徑要求不能相交，恰好對應(yīng)于匹配中兩匹配邊不能有公共端點。二分圖最小路徑覆蓋解釋：于是求最大匹配后，不能被匹配上的點，即是路徑的最后一個點。有多少個不能被匹配的點，就有多少條路徑存在。路徑數(shù)=原點數(shù)－匹配邊數(shù)。因此我們使匹配邊數(shù)最大，即是使路徑數(shù)最小。二分圖最小路徑覆蓋例題：某汽車運輸公司需要安排他們的運送線路，已知從某地點X，坐標(biāo)為（a，b），到某地點Y，坐標(biāo)為（c，d）需要的時間為|a-c|+|b-d|分鐘，現(xiàn)給出所有運送安排，求使用最少的車來完成該運送安排二分圖最小路徑覆蓋SampleInput2208:00101191608:079161011208:00101191608:069161011SampleOutput12二分圖最小路徑覆蓋解法：每條計劃作為一個節(jié)點，令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ò)的邊答案=頂點數(shù)–最大匹配數(shù)二分圖最優(yōu)匹配二分圖最優(yōu)匹配（帶權(quán)最大匹配）：二分圖的每條邊上帶有權(quán)值，求一個匹配使得匹配邊上的權(quán)值和最大。實際問題：每個工人操作不同機(jī)器的效率不同，如何合理分配機(jī)器，使得效率總和達(dá)到最佳？每對男女之間的好感度不同，如何配對使得總的好感度最高？二分圖最優(yōu)匹配KM算法：基本概念：可行頂標(biāo)與相等子圖可行頂標(biāo)是一個關(guān)于節(jié)點的函數(shù)L且對于每條邊(x，y)滿足L(x)+L(y)>=w(x,y)相等子圖是指只包含L(x)+L(y)=w(x,y)的邊的子圖。定理：如果相等子圖有完備匹配（包含所有點的匹配），則該匹配是最大權(quán)匹配。二分圖最優(yōu)匹配KM算法的關(guān)鍵：通過適當(dāng)?shù)匦薷目尚许敇?biāo)從而使相等子圖有完備匹配，于是就可以得到最優(yōu)匹配。設(shè)頂點Xi的頂標(biāo)為a[i]，頂點Yi的頂標(biāo)為b[i]。初始時，a[i]為與Xi相關(guān)聯(lián)的邊的最大權(quán)值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立。二分圖最優(yōu)匹配若相等子圖中不包含完備匹配時，就適當(dāng)修改頂標(biāo)以擴(kuò)大相等子圖，直到找到完備匹配為止當(dāng)從Xi尋找交錯路失敗后，得到一棵交錯樹，它的所有葉子節(jié)點都是X節(jié)點，取所有左側(cè)點i在樹中而右側(cè)j不在樹中的邊(i,j)，計算d=min{a[i]+b[j]-w[i][j]}。交錯樹中所有左側(cè)點頂標(biāo)-d，右側(cè)點頂標(biāo)+d…二分圖最優(yōu)匹配對于圖中所有的邊(i,j)，可以看到若i和j都不在交錯樹中，邊(i,j)仍不屬于相等子圖若i和j都在交錯樹中，邊(i,j)仍然屬于相等子圖若i在交錯樹中，j不在交錯樹中，a[i]+b[j]減少，邊(i,j)有可能加入到相等子圖中每次更新頂標(biāo)，至少有一條邊新加入相等子圖，匹配也就可能繼續(xù)擴(kuò)大二分圖最優(yōu)匹配例題：在一片花園中，有人（’H’），有屋（’m’），有空地（’.’），且人和屋子的數(shù)量一致，每個屋子只能住一個人，每個人只能上下左右四個方向行走，現(xiàn)在給你花園的現(xiàn)狀，求使每個人都能進(jìn)到屋子里的最小步數(shù)二分圖最優(yōu)匹配SampleInput

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

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