「补档计划」k-d 树

k-d 树(k-dimensional tree)是在 kk 维欧几里德空间组织点的数据结构。k-d 树可以使用在多种应用场合,如多维键值搜索(例:范围搜寻及最邻近搜索)。k-d 树 是空间二分树(Binary space partitioning)的一种特殊情况。而在算法竞赛中,k-d树往往用于在二维平面内的信息检索,这里主要指二维 k-d 树。

「补档计划」最小费用流 Primal Dual 算法

求解最小费用流的算法有很多,如增广路算法(SPFA),消圈算法,zkw 算法,Primal Dual 算法及网络单纯形,其中消圈算法和网络单纯形较为通用但速度不够快或编程复杂度过高,SPFA 和 zkw 在不同的图上各有所长,这里介绍不容易被卡掉的 Primal Dual 算法。

注意: Primal Dual 算法也不能适用于存在负圈的图。