這個(gè)有必要自己寫一系列的文章和標(biāo)程來整理，盡量使用英文和大家經(jīng)常表述的中文來表達(dá)。。。
在中英文表達(dá)這個(gè)問題上，嚴(yán)重影響了學(xué)習(xí)資料的通用性。。。。
必須知識：最短路徑問題
1.Dijkstra
適用于滿足所有權(quán)系數(shù)大于等于0（lij≥0）的網(wǎng)絡(luò)最短路問題，能求出起點(diǎn)v1到所有其他點(diǎn)vj的最短距離；
樸素的Dijkstra算法復(fù)雜度為O(N^2)，堆實(shí)現(xiàn)的Dijkstra復(fù)雜度為O(NlogN).
2.bellman-ford
適用于有負(fù)權(quán)系數(shù)，但無負(fù)回路的有向或無向網(wǎng)絡(luò)的最短路問題，能求出起點(diǎn)v1到所有其它點(diǎn) vj的最短距離。bellman-ford算法復(fù)雜度為O(V*E)。
3.Floyed
適用于有負(fù)權(quán)系數(shù)，可以求出圖上任意兩點(diǎn)之間的最短路徑。DP思想的算法，時(shí)間復(fù)雜度為O(N^3);
for ( k= 1; k<= n; k++)
for ( i= 1; i<= n; i++)
if (graph[i][k]!=INF)
for ( j= 1; j<= n; j++)
if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])
graph[i][j]= graph[i][k]+ graph[k][j];
NO.1 s-t最大流
兩大類算法
1.增廣路算法
Ford-Fulkerson算法: 殘留網(wǎng)絡(luò)中尋找增加路徑
STEP0：置初始可行流。
STEP1：構(gòu)造原網(wǎng)絡(luò)的殘量網(wǎng)絡(luò)，在殘量網(wǎng)絡(luò)中找s－t有向路。如果沒有，算法得到最大流結(jié)束。否則繼續(xù)下一步。
STEP2：依據(jù)殘量網(wǎng)絡(luò)中的s－t有向路寫出對應(yīng)到原網(wǎng)絡(luò)中的s－t增廣路。對于增廣路中的前向弧，置s(e)＝u(e)- f(e)。對于反向弧，置s(e)＝f（e） STEP3：計(jì)算crement=min{s（e1），s（e2），…，s（ek）}
STEP4：對于增廣路中的前向弧，令f(e)＝f(e)＋crement；對于其中的反向弧，令f(e)＝f(e)-crement，轉(zhuǎn)STEP1。
關(guān)鍵點(diǎn):尋找可增廣路。決定了算法復(fù)雜度。
實(shí)現(xiàn)：Edmonds-Karp 通過采用了廣度優(yōu)先的搜索策略得以使其復(fù)雜度達(dá)到O(V*E^2)。
優(yōu)化—> Dinic算法(*)
Dinic算法的思想是為了減少增廣次數(shù)，建立一個(gè)輔助網(wǎng)絡(luò)L，L與原網(wǎng)絡(luò)G具有相同的節(jié)點(diǎn)數(shù)，但邊上的容量有所不同，在L上進(jìn)行增廣，將增廣后的流值回寫到原網(wǎng)絡(luò)上，再建立當(dāng)前網(wǎng)絡(luò)的輔助網(wǎng)絡(luò)，如此反復(fù)，達(dá)到最大流。分層的目的是降低尋找增廣路的代價(jià)。
算法的時(shí)間復(fù)雜度為O(V^2*E)。其中m為弧的數(shù)目，是多項(xiàng)式算法。鄰接表表示圖，空間復(fù)雜度為O(V+E)。
2.預(yù)流推進(jìn)算法
一般性的push-relabel算法: 時(shí)間復(fù)雜度達(dá)到O(V^2*E)。(*)
relabel-to-front算法->改進(jìn)
最高標(biāo)號預(yù)流推進(jìn):時(shí)間復(fù)雜度O(V^2*sqrt(E))
NO2. 最小費(fèi)用最大流
求解最小費(fèi)用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟1時(shí)選一條非飽和路時(shí)，應(yīng)選代價(jià)和最小的路，即最短路。
步驟1. 選定一條總的單位費(fèi)用最小的路，即要給定最小費(fèi)用的初始可行流，而不是包含邊數(shù)最小的路。
步驟2. 不斷重復(fù)求最大流的步驟來進(jìn)行，直到?jīng)]有飽和路存在為止。然后計(jì)算每個(gè)路的總費(fèi)用。
和Edmonds-Karp標(biāo)號算法幾乎一樣，因?yàn)檫@兩種算法都使用寬度優(yōu)先搜索來來尋找增廣路徑，所以復(fù)雜度也相同，都是O(V*E^2)。
連續(xù)最短路算法 + 線性規(guī)劃對偶性優(yōu)化的原始對偶算法(*)
傳說中，沒見過，據(jù)說復(fù)雜度是O(V^3)
NO3. 有上下屆的最大流和最小流（通過添加點(diǎn)來進(jìn)行轉(zhuǎn)化）(*)
NO4. 相關(guān)圖論算法
二分圖最大匹配： 加s和t構(gòu)造最大流
專用算法：hungary算法 O(M*N)
二分圖最佳匹配： 加s和t構(gòu)造最小費(fèi)用最大流
專用算法：KM算法
樸素的實(shí)現(xiàn)方法,時(shí)間復(fù)雜度為O(n^4)
加上松弛函數(shù)O(n^3)
最小路徑覆蓋：
頂點(diǎn)數(shù)－二分圖的最大匹配
s-t最小邊割集：
最大流最小割定理：最小割等于最大流
普通最小邊割集：
Stoer-Wagner Minimum Cut O(n^3)
二分圖的最大獨(dú)立集：
N - 二分圖的最大匹配（POJ monthly）girls and boys
反證法證明
普通圖的最大獨(dú)立集是np問題。(*)
http://hi.baidu.com/flymouse/blog/item/c4752df57a779325bc310982.html/cmtid/d9239e2f6cde91351e308925