【速查】知名竞赛算法实装
(本文未经许可禁止转载)
树
红黑树
红黑树 = 234树 = OrderedSet<k> = OrderedDictionary<k,v>
图
Dijkstra
起点0其它点∞、循环：【找未查中最小点、标记为已查、累加边权min更新邻接点、若更新则记录上一点】、逆向输出上一点。
- 边：
<int:length>[][] - 点：
<int:distance,int:lastid,bool:found>[]
Dijkstra假设了所有边权非负
O(|E|+|V|log|V|)（此复杂度有Sparse假设）
Bellman-Ford
起点0其它点∞、无更新为止遍历所有点：【若当前点∞跳过、累加边权min更新邻接点、若更新则记录上一点】、逆向输出上一点。
- 边：
<int:length>[][] - 点：
<int:distance,int:lastid>[]
Bellman ford支持负边，但比Dijkstra时间复杂度高
O(|E||V|)（此复杂度有Sparse假设）
或者干脆不判断是否更新，直接进行|V|-1次循环(同时避免负权环死循环)。参考>>>
可以记录更新的点作为下一次松弛候选（SPFA）
SPFA
初始点放入队列、循环：【队列中取点、累加边权min更新邻接点、对于“严格”更新成功的邻接点、若不在队列中则放入队列】
术语：“严格、非严格更新”只在本文中使用：
严格更新：if(a>b) //success;
非严格更新：if(a>=b) //success;
Floyd
按顺序三层循环k,i,j：【a[i][j] min= a[i][k] + a[k][j];】
- 边：
<int:length>[][]
最小生成树(MST)
创建点UF、小到大遍历边权：【边两点不在同集时Union】、输出UF。
- 边：
<int:length>[][] - UF：
<int:setid>[]
网络流
基本假设：源入度=0、汇出度=0
最大流问题(Endmonds-Karp)
流量分配全部设0、循环：【BFS寻增广路更新流量分配】
- 边：
<int:capacity>[][]
最大流问题：有向赋权（容量）图中寻找源汇间最大流量分布
残量网络：描述流量和容量之间的可调整关系的网络
（正向：容量分布-流量分布 反向：流量分布 ）反向边解释
例如：A==1/3==>B的残量网络为：A==2==>B & A<==1==B
增广路：残量网络中的一条路径
增广路定理：若源汇间无增广路，则流量分布达到最大。
最小费用最大流问题
流量分配全部设0、循环：【Bellman-Ford寻最小费用增广路更新流量分配】
费用残量网络：描述费用调整关系的网络
例如：A--1/3 $5-->B的费用残量网络为：A== 2*$5 ==>B & A<== -1*$5 ==B
即：增广时花钱、反增广时退钱。所以有负权，要用Bellman-Ford
费用增广路：费用残量网络中的一条路径