【速查】知名竞赛算法实装
(本文未经许可禁止转载)
树
- 红黑树 = 234树 =
Set<k>
=Dictionary<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
费用增广路:费用残量网络中的一条路径