* 求有向图的强连通分支 (Strongerst Connected Component)(cut)
o Kosaraju算法
o Gabow算法
o Tarjan算法
* 求最小生成树 (Minimal Spanning Trees) (cut)
o Kruskal算法(cut边更新)
o Prim算法(cut点更新)
* 最短路径问题(cut)
o SSSP(Single-source Shortest Paths)
* Dijkstra算法 (cut)
* Bellman-Ford算法(SPFA算法)(cut)
o APSP(All-pairs Shortest Paths)
* Floyd-Warshall算法(cut)
* Johnson算法
* 网络流问题
o 最大网络流
* 增广路算法
* Ford-Fulkerson算法
* Edmonds-Karp算法
* Dinic
* 预流推进算法
o 最小费用流
* 图匹配问题 （部分cut）
o 匈牙利算法(cut)
o Kuhn-Munkres算法
- o Edmonds' blossom-contraction 算法
次小生成树(K小生成树)
最小树形图
最小K限制度生成树
最优比率生成树(0-1分数规划)
第K最短路
LP问题以及Primal-Dual(单纯型法)
最大流(最短增广路、最高标号预流推进)
最小费用流(最小费用路、Primal-Dual算法)
二分图最优匹配(原始-对偶KM算法)
acm.pku.edu.cn 的：
最小生成树
1251(cut)
1258(cut)
1789(cut)
2485(cut)
最短路
1062(cut 建模的时侯要注意 ，不断建符合等级差的图 做最短路径)
1125（cut 做全源最短路
再对以每各点为根的树：找最长的边
再对每棵树的最长边 找最短的那一条
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
起点到n点 路径上 所能承受的 最大重量的车
dist[k] 源点到k 路径中最小的那个边权值 mat[k][i]边k-i权值
取路径 dist[k] 和mat【k】【i】边最大那个 更新 dist[i] )
2253(cut 要求的与 1797相反)
Johnson算法适用于求All Pairs Shortest Path. Johnson算法应用了重标号技术，先进行一次Bellman-Ford算法，然后对原图进行重标号，w'(i,j)=h[i]-h[j]+w(i,j)。然后对每个点进行一次Dijkstra，每次Dijkstra的复杂度为O(nlogn+m)，于是算法复杂度为O(n^2logn+m)。
posted on 2008-10-26 23:33
爬 阅读(985)
评论(3) 编辑 收藏 引用 所属分类:
algorithm