【速查】知名竞赛算法实装

           

树

红黑树

红黑树 = 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
费用增广路：费用残量网络中的一条路径