* 求有向圖的強(qiáng)連通分支 (Strongerst Connected Component)(cut)
o Kosaraju算法
o Gabow算法
o Tarjan算法
* 求最小生成樹 (Minimal Spanning Trees) (cut)
o Kruskal算法(cut邊更新)
o Prim算法(cut點(diǎn)更新)
* 最短路徑問題(cut)
o SSSP(Single-source Shortest Paths)
* Dijkstra算法 (cut)
* Bellman-Ford算法(SPFA算法)(cut)
o APSP(All-pairs Shortest Paths)
* Floyd-Warshall算法(cut)
* Johnson算法
* 網(wǎng)絡(luò)流問題
o 最大網(wǎng)絡(luò)流
* 增廣路算法
* Ford-Fulkerson算法
* Edmonds-Karp算法
* Dinic
* 預(yù)流推進(jìn)算法
o 最小費(fèi)用流
* 圖匹配問題 （部分cut）
o 匈牙利算法(cut)
o Kuhn-Munkres算法
- o Edmonds' blossom-contraction 算法
次小生成樹(K小生成樹)
最小樹形圖
最小K限制度生成樹
最優(yōu)比率生成樹(0-1分?jǐn)?shù)規(guī)劃)
第K最短路
LP問題以及Primal-Dual(單純型法)
最大流(最短增廣路、最高標(biāo)號預(yù)流推進(jìn))
最小費(fèi)用流(最小費(fèi)用路、Primal-Dual算法)
二分圖最優(yōu)匹配(原始-對偶KM算法)
acm.pku.edu.cn 的：
最小生成樹
1251(cut)
1258(cut)
1789(cut)
2485(cut)
最短路
1062(cut 建模的時(shí)侯要注意 ，不斷建符合等級差的圖 做最短路徑)
1125（cut 做全源最短路
再對以每各點(diǎn)為根的樹：找最長的邊
再對每棵樹的最長邊 找最短的那一條
int ans=maxint;
for(i=1;i<=n;i++){
tmp=-1;
for(j=1;j<=n;j++){
tmp=max(tmp,a[i][j]);
}
if(tmp < ans){ans=tmp;val=i;}
}
）
1797(cut
起點(diǎn)到n點(diǎn) 路徑上 所能承受的 最大重量的車
dist[k] 源點(diǎn)到k 路徑中最小的那個(gè)邊權(quán)值 mat[k][i]邊k-i權(quán)值
取路徑 dist[k] 和mat【k】【i】邊最大那個(gè) 更新 dist[i] )
2253(cut 要求的與 1797相反)
Johnson算法適用于求All Pairs Shortest Path. Johnson算法應(yīng)用了重標(biāo)號技術(shù)，先進(jìn)行一次Bellman-Ford算法，然后對原圖進(jìn)行重標(biāo)號，w'(i,j)=h[i]-h[j]+w(i,j)。然后對每個(gè)點(diǎn)進(jìn)行一次Dijkstra，每次Dijkstra的復(fù)雜度為O(nlogn+m)，于是算法復(fù)雜度為O(n^2logn+m)。
posted on 2008-10-26 23:33
爬 閱讀(1006)
評論(3) 編輯 收藏 引用 所屬分類:
algorithm