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