$F o r e w o r d$

开始之前的碎碎念，为什么想我这样的一个蒟蒻都开始写我自己的ACM模板了

首先自己写自己的模板可以在赛场上更加亲切，~~并且能保证自己的超长头文件和宏定义不会写错~~。写一些模板也可以使我更加地熟悉这些算法，并且我的模板是更适合我自己的，因为我比较菜，所以我的模板会附带一些注释和我自己对这个算法的简单理解和易错点，以及我刷题得到的一些经验教训，一些提示的话。更重要的是能帮助我自己复习，毕竟很多算法学完了没几天就忘得差不多了，所以这种学会讲给别人听的学习方法（写博客，就像中学时期的错题本一样）也挺适合于ACM的，给大家提供一个学习的思路，大佬勿喷。

这个模板我可能会更新的很慢，~~主要取决于我的学习速度~~ 所以不要着急哈。

准备写这个模板还有一个原因是我看了一位学姐的模板，深受启发，但是学姐很明显是已经学完了全部的算法，所以更新的非常快，我就不一样了，学到哪儿更到哪儿。

我的模板大概会跟学姐的模板格式差不多吧。

以后我的模板要每一句都加上注释，方便我太久不用快速了解每一句的作用，这样在写模板改编题的时候改得动模板（~~主要还是因为我太菜了~~ ）

$Text\ Part$

C++头文件汇总

输入输出优化

一、 $S T L$ 标准模版库

比STL还STL？——__gnu_pbds食用教程

${\ }$ ${\ }$ STL
${\ }$ ${\ }$ map
${\ }$ ${\ }$ queue类

二、动态规划 ${\ \ \ }$ $dynamic\ programming$

~~动态规划要什么模板~~

${\ }$ 最长上升子序列与最长公共子序列

三、字符串 ${\ \ \ \ \ }$ $S t r i n g$

${\ }$ 1.KMP算法

${\ }$ 2.trie树（字典树）

${\ }$ ${\ }$ ${\ }$ 3.AC自动机

模板有多少个模式串在文本串里出现过
建fail树dfs求每个模式串在文本串中的出现次数
ac自动机fail树上dfs序建可持久化线段树

${\ }$ ${\ }$ ${\ }$ 4.字符串哈希

四、数据结构 ${\ \ \ }$ $S t r u c t u r e$

${\ }$ ${\ }$ ${\ }$ 1.并查集

朴素并查集
维护size的并查集
维护到祖宗节点距离的并查集
路径压缩和按秩合并
边带权
扩展域

${\ }$ ${\ }$ ${\ }$ 2.树状数组

树状数组求逆序对
区间加、求单点值
区间加、区间求和
单点修改、区间求最值
实时求出剩余的数中的第k小的数（树状数组+二分）

${\ }$ ${\ }$ ${\ }$ 3.线段树

懒惰标记
扫描线法
二维线段树 – 矩形树
三维线段树 – 空间树
线段树上二分（查询某个点向一个方向连续值相同区间）

${\ }$ ${\ }$ ${\ }$ 4.平衡树 – treap

普通平衡树：
operator 1 : 插入一个数
operator 2 : 删除一个数
operator 3 : 通过数值找排名
operator 4 : 通过排名找数值
operator 5 : 找到严格小于key的最大数（前驱）
operator 6 : 找到严格大于key的最小数（后继）

${\ }$ ${\ }$ ${\ }$ 5.平衡树 – FHQ treap（无旋treap）

普通平衡树：
operator 1 : 插入一个数
operator 2 : 删除一个数
operator 3 : 通过数值找排名
operator 4 : 通过排名找数值
operator 5 : 找到严格小于key的最大数（前驱）
operator 6 : 找到严格大于key的最小数（后继）
（按权值分裂 / 按排名分裂）
文艺平衡树：
区间操作：翻转一个区间
可持久化序列 ：
支持三个操作：
1 l r，翻转l到r的区间；
2 l r，询问l的到r的区间和；
3 p，回到p时刻。

${\ }$ ${\ }$ ${\ }$ 6.平衡树 – splay

五、图论 ${\ \ \ \ \ \ \ \ \ }$ $Graph\ theory$

${\ }$ ${\ }$ 1.树与图的遍历

${\ }$ ${\ }$ ${\ }$ 2.最短路合集

一、线段树优化的Dijkstra
1.普通线段树
2.最强的zkw线段树优化版本
3.路径还原
二、可以处理负权值的SPFA
SPFA的SLF优化
SPFA的LLL优化
SPFA的DFS优化（适用于负环的判断）
三、两种分层图最短路
分层次
分维度
四、Floyd算法，传递闭包

${\ }$ ${\ }$ ${\ }$ 3.k短路

k短路
Dijkstra + A*

${\ }$ ${\ }$ ${\ }$ 4.欧拉路、欧拉回路（一笔画问题）

非递归版
普通递归版
Hierholzers算法（输出字典序最小的答案）
Fleury算法
究极优化版

${\ }$ ${\ }$ ${\ }$ 5.最小生成树

一、kruskal算法
二、prim算法
三、Boruvka算法
四、生成森林问题（K颗树）
五、最小生成树的唯一性
六、严格次小生成树
LCA优化的次小生成树
七、瓶颈生成树
八、最小瓶颈路
单次查询
多次查询
九、Kruskal 重构树

${\ }$ ${\ }$ ${\ }$ 6.最小树形图（朱刘算法）

1.给定一个根的有向图的最小树形图
2.为给定根的树形图
3.判断无解的方法

${\ }$ ${\ }$ ${\ }$ 7.负环（超时高效优化技巧）、01分数规划

1.负/正环判断
2.01分数规划

${\ }$ ${\ }$ ${\ }$ 8.树上问题

一、树的直径
树形DP / 两次DFS / BFS（找到直径的两个端点）
二、动态修改树的边权并求每个时刻的直径（线段树）
三、树的重心

${\ }$ ${\ }$ ${\ }$ 9.最近公共祖先及其应用

一、LCA的在线倍增算法
二、LCA的离线Tarjan算法
三、树上差分
四、次小生成树（LCA优化）

${\ }$ ${\ }$ ${\ }$ 10.有向图的连通性

1.最大半连通子图
2.有向图的tarjan模板
3.去重缩点模板
4.按拓扑序递推模板
5.Tarjan算法求有向图强连通分量并缩点
6.几个结论
（1）一个有向图最少给多少个点提供资源（有连边的点之间可以互相传达资源）使得所有的点都拥有资源
（2）连多少条边使得整个有向图变为强连通图
（3）最大可以增加多少条边使得这个图仍然不是强连通图

${\ }$ ${\ }$ ${\ }$ 11.无向图的连通性

1.tarjan算法求无向图的桥、边双连通分量并缩点
2.tarjan算法求无向图的割点、点双连通分量并缩点
3.结论：变成边双连通分量所需要新建的边数
4.动态求解当前图中的桥的数目（割边缩点+并查集+lca+优化 $O (m + q l o g n)$ ）

${\ }$ ${\ }$ ${\ }$ 12.2 – SAT问题

${\ }$ ${\ }$ ${\ }$ 13.拓扑排序

1.toposort模板
2.已有编号求字典序最小的拓扑序（优先队列）
3.给所有点分配编号使得拓扑序的字典序最小（反图、优先队列）

${\ }$ ${\ }$ ${\ }$ 14.二分图

1.染色法判断二分图
2.增广路的性质
3.一些二分图的概念和定理
4.二分图最大匹配
5.匈牙利算法
6.二分图匹配模型的两个要素
7.二分图最小点覆盖的一个要素
8.DAG的最小路径点覆盖
9.DAG的最小可重复路径点覆盖
10.最小可重复路径点覆盖模板

${\ }$ ${\ }$ ${\ }$ 15.KM算法（O(n^3)）（二分图最大权完美匹配）

${\ }$ ${\ }$ ${\ }$ 16.一般图最大匹配（带花树）

${\ }$ ${\ }$ ${\ }$ 17. 判断一个图是否为树（有向图以及无向图）

六、网络流 ${\ \ \ \ \ \ }$ $Network\ flow$

${\ }$ ${\ }$ ${\ }$ 1.最大流

1.Edmonds−Karp
2.Dinic
3.ISAP
4.Push−RelabelPush−Relabel 预流推进算法
通用的预流推进算法
5.HLPP 算法

${\ }$ ${\ }$ ${\ }$ 2.最小割

一、集合划分模型
二、点边转化
三、最小割的可行边与必须边
四、二分图的可行边和必须边
五、平面图最小割
六、最小割的一些小技巧
1.记录划分方案
2.求割边数量
3.求最小边的最小割
4.输出任意一种最小割的方案
5.判断一条边是否满流
6.判断某一条边是否可能为最小割中的一条
7.判断某条边是否一定出现在最小割中

${\ }$ ${\ }$ ${\ }$ 3.费用流

一、最小费用最大流
类dinic模板
二、最大费用最大流
解决二分图带权最大匹配
三、费用提前计算+动态开点

七、数学 ${\ \ \ \ \ \ \ \ \ }$ $Number\ Theory$

${\ }$ ${\ }$ ${\ }$ 1.质数筛法

试除法判定质数
线性筛法
二次筛法

${\ }$ ${\ }$ ${\ }$ 2.Min_25 筛法求素数和

${\ }$ ${\ }$ ${\ }$ 3 欧几里得算法与唯一分解定理

${\ }$ ${\ }$ ${\ }$ 4.分解质因数

试除法分解质因数
Pollard Rho因数分解
快速阶乘质因数分解

${\ }$ ${\ }$ ${\ }$ 6.基于值域预处理的快速 GCD

${\ }$ ${\ }$ ${\ }$ 6.快速求n所有因数（快于sqrt(n) ）

${\ }$ ${\ }$ ${\ }$ 10.莫比乌斯反演

${\ }$ ${\ }$ ${\ }$ 11.线性基

插入和判断
查询异或最值
查询k小值

${\ }$ ${\ }$ ${\ }$ 《算法竞赛中的初等数论》（信奥 / 数竞 / ACM）前言、后记、目录索引（十五万字符的数论书）

${\ }$ ${\ }$ ${\ }$ 《博弈论全家桶》（ACM / OI）（超全的博弈论 / 组合游戏大合集）

${\ }$ ${\ }$ ${\ }$ 《线性代数全家桶》（ACM / OI）

${\ }$ ${\ }$ ${\ }$ 《生成函数全家桶》超级简单的生成函数从入门到升天教程

${\ }$ ${\ }$ ${\ }$ 小学生都能看懂的群论从入门到升天教程《群论全家桶》附带大量超高质量解题报告

八、计算几何 ${\ \ \ }$ $G e o m e t r y$

${\ }$ ${\ }$ ${\ }$ 1.计算几何注意事项

${\ }$ ${\ }$ ${\ }$ 2.计算几何相关公式大全

${\ }$ ${\ }$ ${\ }$ 3.二维几何基础

1.基本运算
1.1 判断正负函数(sgn)
1.2 点积（数量积、内积）(Dot)
1.3 向量积，叉积(Cross)
1.4 取模（求长度）(Length)
1.5 计算两向量夹角(Angle)
1.6 计算两向量构成的平行四边形有向面积(Area2)
1.7 计算向量逆时针旋转后的向量(Rotate)
1.8 计算向量逆时针旋转九十度的单位法线(Normal)
1.9 判断折线（向量）bc是不是向（向量）ab的逆时针方向（左边）转向(ToLeftTest)
1.10 点绕着 p 点逆时针旋转 angle(rotate)
1.11 判断点和直线关系(relation)
1.12 复数表示
2.点与线
2.1 直线的实现(Line)
2.2 判断点在直线上
2.3 计算两直线交点(Get_line_intersection)
2.4 计算点到直线的距离(Distance_point_to_line)
2.5 计算点到线段的距离(Distance_point_to_segment)
2.6 求点在直线上的投影点(Get_line_projection)
2.7 判断点是否在线段上(OnSegment)
2.8 判断两线段是否相交（不算在端点处相交）(segment_proper_intersection)
2.9 判断两线段是否相交（包含端点处相交）(Segment_proper_intersection)
2.10 判断点是否在一条线段上(不含端点)(on_segment)
2.11 两向量的关系(parallel)
2.12 两直线关系(linecrossline)
3.多边形
3.0.三角形
3.0.1 三角形四心
3.0.2向量求三角形垂心(getcircle)
3.1.0 正多边形的一些性质和概念
3.1 求多边形面积(convex_polygon_area)
3.2 判断点在多边形内(is_point_in_polygon)
3.3 判断点在凸多边形内
3.4 求多边形重心(barycenter)
3.5 判定凸多边形(is_convex)
3.6 判点在凸多边形内或多边形边上(inside_convex)
3.7 判点在任意多边形内(inside_polygon)
3.8 判线段在任意多边形内(inside_polygon)
3.9 多边形切割(常用于半平面交)
4.圆
4.1 圆与直线交点(getLineCircleIntersection)
4.2 求两圆交点(get_circle_circle_intersection)
4.3 点到圆的切线(get_tangents)
4.4 两圆的公切线(get_tangents)
4.5 两圆相交面积(AreaOfOverlap)
4.6 模板合集
4.7 判直线和圆相交(intersect_line_circle)
4.8 判线段和圆相交(intersect_seg_circle)
4.9 判圆和圆相交(intersect_circle_circle)
4.10 计算圆上到点p最近点(dot_to_circle)
4.11 计算直线/线段与圆的交点（intersection_line_circle）
4.12 计算圆与圆的交点（intersection_circle_circle）
4.13 求圆外一点对圆的两个切点(TangentPoint_PC)
4.14 求三角形的外接圆(get_circumcircle)
4.15 求三角形的内接圆(get_incircle)
4.16 二维几何6 合一！
4.17 经纬度转换为空间坐标
4.18 球面距离
4.19 三点确定一圆
4.20 两个圆的关系(relationcircle)
5.网格
5.1 多边形上的网格点个数
5.2 多边形内的网格点个数
6.一些函数/定理/应用
6.1 欧拉定理
6.2 Pick定理（根据点在多边形内和边界的个数求面积）
6.3 判断四点共面（混合积）

${\ }$ ${\ }$ ${\ }$ 4. 二维几何常用算法

1.平面扫描
2.凸包
Andrew算法
直线两点式转为一般式使用公式O(1)计算点到直线距离
判断点是否在凸包内
3.旋转卡壳
4.半平面交
有向直线
O(nlogn)O(nlogn)的半平面交
二分 + 半平面交
5.闵可夫斯基和
6.平面区域

${\ }$ ${\ }$ ${\ }$ 5. 三维几何基础

一、三维基础操作
1.1 三维点积(Dot3)
1.2 三维叉积(Cross3)
1.3 矢量差（Subt）
1.4.1 返回ab，ac，ad的混合积(Volume6)
1.4.2 四面体体积(Volume6)
1.5 求四面体的重心(Centroid)
1.6 凸多面体的重心
1.7 二面角
二、三维点线面
2.1 取平面法向量(NormalVector)
2.2 求两点距离(TwoPointDistance)
2.3 点p到平面的距离(DistanceToPlane)
2.4 点p在平面上的投影(GetPlaneProjection)
2.5 直线与平面的交点(LinePlaneIntersection)
2.6 空间直线距离(LineToLine)
2.7 点到直线的距离(DistanceToLine)
2.8 点到线段的距离(DistanceToSeg)
2.9 求异面直线与的公垂线对应的s(LineDistance3D)
2.10 p1和p2是否在线段a-b的同侧(SameSide)
2.11 判断点P是否在三角形中(PointInTri)
2.12 三角形P0、P1、P2是否和线段AB相交(TriSegIntersection)
2.13 空间两三角形是否相交(TriTriIntersection)
2.14 空间两直线上最近点对返回最近距离(SegSegDistance)
2.15判断P是否在三角形A, B, C中，并且到三条边的距离都至少为mindist(InsideWithMinDistance)
2.16判断P是否在凸四边形中，并且到四条边的距离都至少为mindist(InsideWithMinDistance)
三、三维凸包
3.1 加干扰防止多点共面(add_noise)
3.2 凸包的定义(Face)
3.3 增量法求三维凸包(CH3D)
3.4 凸多面体(ConvexPolyhedron)
3.5 给三维凸包求出重心到各面的最小距离。

九、多项式 $\ \ \ \ \ \ \ Polynomial$

骄傲地增加了多项式专题的模板hhh

${\ }$ ${\ }$ ${\ }$ 1. 快速傅里叶变换（FFT）

${\ }$ ${\ }$ ${\ }$ 2.【学习笔记】多项式全家桶

十、其他 ${\ \ \ \ \ \ \ \ \ \ }$ $O t h e r$

${\ }$ ${\ }$ ${\ }$
${\ }$ ${\ }$ ${\ }$ 常用函数总结

全排列 | 读写优化 | 返回容器内最大最小值 | 复制函数 | 容器删除函数 | 容器填充函数 | 查找函数 | 字符串转换整数 | 欧拉筛 | 快速幂 | 快速乘 | 截取部分字符串函数

${\ }$ ${\ }$ ${\ }$ 高精度计算

重载运算符的高精加减乘除

${\ }$ ${\ }$ 离散化

繁凡的ACM模板完整目录

繁凡的ACM模板的全部内容的 PDF 版本全部开源啦！可以直接打印哦！详见：我的所有优质博客全部开源啦（我自己原创的《ACM模板》《算法全家桶》《算法竞赛中的初等数论》《数据结构知识梳理》）

ACM模板…1
一、C++头文件汇总…13
二、动态规划 …16
∮ 1. 背包 …16
∮ 2. 树形DP …19
∮ 3. 数位DP …20
∮ 4. DP 的优化…22
∮ 5. 插头 DP …27
∮ 6. 最长上升子序列与最长公共子序列 …30
6.1 最长上升子序列（LIS）…30
6.1.1 树状数组优化O(nlogn)…30
6.2 最长公共子序列（LCS）…31
6.2.1 转换成LIS优化O(nlogn)…31
三、字符串…32
∮ 1. KMP …32
∮ 2. Trie树 …33
2.1 Trie树模板 …33
2.2 可持久化trie树、求最大区间异或和…35
∮ 3. AC自动机 …36
3.1 求有多少个模式串在文本串里出现过…37
3.2 建fail树dfs求每个模式串在文本串中的出现次数…38
3.3 ac自动机fail树上dfs序建可持久化线段树…40
∮ 4. 字符串哈希 …43
4.1 字符串哈希…43
4.2 二分+哈希…44
∮ 5. 字符串的最小表示…44
∮ 6. manacher算法（O(n)判断回文串）…46
∮ 7. 后缀数组（SA）…46
7.1 DA（倍增算法O(nlogn)）…47
DC3 模板 ( 时间复杂度O(N),空间复杂度O(3N) )…48
∮ 8. 后缀自动机（SAM） …49
8.1 求子串最大出现次数…49
8.2 求不同子串的种类…49
8.3 长度为k的字符串的个数…49
8.4 计算所有子串的和（0-9表示）…49
8.5 给定模式串 s，n 个匹配串 str…50
8.6 求每个匹配串的循环同构能够匹配的子串总数…50
8.7 SAM 转后缀树(子串排序重连后询问第k个字符) …52
∮ 9. 编辑距离…54
四、数据结构 …54
∮ 1. 简单数据结构…55
1.1 单链表…55
1.2 双链表…55
1.3 栈…55
1.4 循环队列…56
1.7 堆 …56
1.8 一般哈希…57
∮ 2. 并查集…58
2.1 朴素并查集…58
2.2 维护size的并查集…58
2.3 维护到祖宗节点距离的并查集…59
2.4 路径压缩和按秩合并…59
2.5 边带权…60
带权并查集求二分图最小环…62
2.6 扩展域…63
2.7 集合中单个元素的删除…64
∮ 3. 树状数组…65
3.1 树状数组求逆序对…65
3.2 区间修改、单点求值…67
3.3 区间修改、区间求和…67
3.4 单点修改、区间求最值…68
3.5 实时求出剩余的数中的第k小的数（树状数组+二分）…69
3.6 离线树状数组（查询区间数的种类）…70
∮ 3.7 二维树状数组…71
3.7.1 单点修改，区间查询…71
3.7.2 区间修改，单点查询 …73
3.7.3 区间修改，区间查询…73
3.7.4 矩阵取反单点查询…74
∮ 4. 线段树…75
4.1 懒惰标记…75
4.2 扫描线法(面积) …78
4.3 扫描线法（周长）…80
4.4 二维线段树 – 矩形树…82
4.5 三维线段树 – 空间树…84
4.6 线段树上二分（查询某个点向一个方向连续值相同区间）…84
4.7 离散数学应用（线段树）开闭区间表示…84
4.8 动态开点+线段树合并优化空间 …87
4.9 权值线段树区间第k小…90
4.10 线段树分治（删除一些边询问是否为二分图）…90
∮ 5. 平衡树…91
5.1 FQH – treap 非旋平衡树…91
5.1.1 按权值分裂…92
5.1.2 按排名分裂…94
5.2 文艺平衡树…98
5.3 可持久化序列 …100
∮ 6. 可持久化线段树(主席树) …103
6.1 查询区间第k大值…103
6.2 （带修改）动态查询区间第k大值…105
∮ 7. 单调栈与单调队列…106
7.1 单调栈…106
7.2 单调队列…108
7.3 单调队列求矩阵的和…108
∮ 8. ST表（静态查询区间最值） …110
8.1 一维RMQ问题…110
8.2 二维RMQ问题…111
∮ 9. 莫队 …112
9.1 基础莫队…112
9.2 带修莫队…116
9.3 回滚莫队…120
4. 树上莫队…123
五、图论…127
∮ 1. 最短路…127
1.1 线段树优化的Dijkstra…128
1.1.1 路径还原…130
1.2 可以处理负权值的SPFA …132
1.2.1 SPFA的SLF优化…133
1.2.2 SPFA的LLL优化…134
1.2.3 SPFA的DFS优化（适用于负环的判断）…134
1.3. 两种分层图最短路…135
1.3.1 分层次…135
1.3.2分维度…136
1.4 Floyd算法，传递闭包…137
1.5 最小环问题…138
∮ 2. 最长路…140
∮ 3. k短路 …141
3.1 两点间 k 短路…143
∮ 4. 欧拉回路…144
4.1 非递归版…145
4.2 普通递归版…145
4.3 Hierholzers算法（输出字典序最小的答案）…146
4.4 Fleury算法…146
4.5 究极优化版…147
4.6 混合图欧拉回路 …149
4.7 中国邮递员问题（欧拉回路、状压DP）…151
∮ 5. 最小生成树 …152
5.1 kruskal算法…152
5.2 prim算法…153
5.3 Boruvka算法…155
5.4 生成森林问题（K颗树）…157
5.5 最小生成树的唯一性…157
5.6 严格次小生成树…158
5.7 LCA优化的次小生成树 …158
5.8 瓶颈生成树…161
5.9 最小瓶颈路…161
5.9.1 单次查询…161
5.9.2 多次查询…161
5.10 Kruskal 重构树…162
5.11 最小生成树计数…164
5.12 曼哈顿最小生成树…166
∮ 6. 最小树形图（朱刘算法）…168
6.1 给定一个根的有向图的最小树形图…168
6.2 为给定根的树形图…169
6.3 判断无解的方法…169
∮ 7. 负环与01分数规划 …169
7.1 判断负环…169
7.2 01分数规划…170
7.3 判负环时TLE的优化技巧：…170
7.4 经验trick…170
7.5 使用stack…171
∮ 8. 树上问题…172
8.1 树的直径…172
8.1.1 树形DP …172
8.1.2 两次DFS / BFS（找到直径的两个端点）…173
8.2 动态修改树的边权并求每个时刻的直径（线段树）…175
8.3 树的重心…176
∮ 9. 最近公共祖先…177
9.1 LCA的在线倍增算法…177
9.2 LCA的离线Tarjan算法…179
9.3 树上差分…180
∮ 10. 有向图的连通性 …184
10.1 tarjan模板…184
10.2 最大半连通子图…186
10.3 tarjan缩点+记忆化搜索…188
10.4 几个有向图连通性的结论…190
∮ 11. 无向图的连通性 …192
11.1 tarjan算法求无向图的桥、边双连通分量并缩点…192
11.2 tarjan算法求无向图的割点、点双连通分量并缩点…194
11.3 结论：变成边双连通分量所需要新建的边数…195
11.4 动态求解当前图中的桥的数目（割边缩点+并查集+lca+优化O(m+qlogn)）…198
∮ 12. 2 – SAT问题…201
12.1 2 – SAT模板…201
12.2 最小字典序解…203
12.3 2 – SAT + 二分答案…205
∮ 13. 拓扑排序…207
13.1 toposort模板…207
13.2 拓扑排序判断是否有环…208
13.3 已有编号求字典序最小的拓扑序（优先队列）…209
13.4 给所有点分配编号使得拓扑序的字典序最小（反图、优先队列）…210
13.5 可达性统计（拓扑排序+bitset优化）…211
1.1 DAG中从每个点出发能到达的点的数量…211
1.2 DAG最多删除多少条边仍可保证其连通性…211
13.6 (2019年南京C题)拓扑排序递推DP经典…212
∮ 14. 二分图（包含全套常用定理性质） …213
14.1 染色法判断二分图…214
14.2 增广路的性质 …215
14.3 一些二分图的概念和定理…215
14.4 增广路定理…216
14.5 二分图最大匹配 …216
14.6 二分图完美匹配…216
14.7 匈牙利算法…216
14.8 二分图匹配模型的两个要素 …217
14.9 二分图最小点覆盖的一个要素…217
14.10 DAG的最小路径点覆盖 …217
14.11 DAG的最小可重复路径点覆盖 …217
14.12 最小可重复路径点覆盖模板 …217
14.13 二分图的多重匹配…219
∮ 15. 一般图最大匹配（带花树） …220
15.1 一般图最大匹配…220
15.2 一般图最大权匹配…222
∮ 16. KM算法（二分图最大权完美匹配） …227
O(n^3)的\tt BFS迭代版本 …227
∮ 17. 最小斯坦纳树(求联通k个关键点最小的代价) …229
∮ 18. 基环树…230
18.1 找环…231
18.2 求基环树森林的直径…232
∮ 19. 支配树/灭绝树…234
∮ 20. 树的最大匹配…237
20.1 树上 DP – 求树的最大匹配数…238
∮ 21. 最大团…238
21.1 Bron-Kerbosch 算法爆搜求最大团…238
21.2 最大独立集转反图最大团…239
∮ 22. 弦图 …241
22.1 弦图的判定…241
22.2 弦图的最小染色问题…242
23. 竞赛图（有向完全图） …243
23.1 兰道定理…243
例题HDU 5873 Football Games…244
23.2 求竞赛图的任意三元环…245
23.3 求竞赛图的哈密顿回路数量的期望…245
24. 哈密顿问题…247
24.1 基本概念…247
24.2 状压DP求最短Hamilton …248
24.3 dfs 搜索求哈密尔顿回路…248
24.4 Dirac 定理下构造无向图的哈密顿回路…249
24.5 N 阶竞赛图下构造有向图的哈密顿通路…252
25. 树的计数…253
25.1 \text{prufer} 序列…253
25.2 \text{prufer} 序列的性质 …253
25.3 \text{Cayley} 公式的推论…253
25.4 【模板】 Prufer 序列…253
六、网络流 …254
∮ 1. 最大流…254
1.1 Dinic …254
1.2 ISAP …256
1.3 Push-Relabel 预流推进算法…258
1.4 通用的预流推进算法…258
1.4.1 HLPP 算法…258
∮ 2. 最小割…260
2.1 集合划分模型…260
2.2 点边转化…262
2.3 最小割的可行边与必须边…263
2.4 二分图的可行边和必须边…264
2.5 平面图最小割…264
2.6 最小割的一些小技巧…265
2.6.1 记录划分方案…265
2.6.2 求割边数量…265
2.6.3 求最小边的最小割…265
2.6.4 输出任意一种最小割的方案…265
2.6.5 判断一条边是否满流…265
2.6.6 判断某一条边是否可能为最小割中的一条…265
2.6.7 判断某一条边是否为最小割中的一条…266
2.6.8 判断某条边是否一定出现在最小割中…266
∮ 3.费用流…266
3.1 最小费用最大流…266
3.1.1类dinic模板…266
3.1.2 ZKW费用流…268
3.2 最大费用最大流…270
3.3 解决二分图带权最大匹配…270
3.4 费用提前计算+动态开点…272
∮ 4. 上下界网络流…272
4.1 无源汇上下界可行流…272
4.2 有源汇有上下界可行流…274
4.3 有源汇上下界最大流…274
4.4 有源汇上下界最小流…276
七、数论…278
∮ 1. 基础数论…278
试除法判定质数 …278
试除法分解质因数 …278
朴素筛法求素数…279
线性筛法求素数 …279
试除法求所有约数 …279
约数个数和约数之和 …280
欧几里得算法 …280
求欧拉函数…280
筛法求欧拉函数…280
快速幂…281
扩展欧几里得算法…281
高斯消元 …281
递归法求组合数 …282
通过预处理逆元的方式求组合数 …282
Lucas定理 …283
分解质因数法求组合数 …283
卡特兰数…285
NIM游戏…285
SG函数…285
∮ 2. 质数筛法…286
线性筛法…286
二次筛法…286
∮ 3. 分解质因数 …287
试除法分解质因数…287
Pollard Rho因数分解…287
快速质因数分解阶乘…288
∮ 4. 线性基 …289
∮ 5. 质数 …290
1.暴力判…290
2.Miller Rabin …290
3.埃氏筛…291
4.欧拉筛…292
5. Min_25 筛法快速求素数和…292
∮ 6. 约数 …293
1.欧几里得 (gcd)…293
2.欧拉函数（埃氏筛）…293
3.欧拉函数（欧拉筛）…294
∮ 7. 同余 …294
1.逆元…294
(1).递推…294
(2).快速幂…294
3.扩展欧拉定理…295
4.扩展欧几里得 (Exgcd)（同余方程）…295
5.中国剩余定理 (CRT)…296
6.扩展中国剩余定理 (EXCRT)…297
7.拔山盖世 / 大步小步 / BSGS (Baby Steps Giant Steps)…297
8.扩展 BSGS (EXBSGS)…298
9.二次剩余…300
10.N 次剩余…301
∮ 8. 类欧几里得算法 …303
∮ 9. 各类反演及数论筛法 …305
1.莫比乌斯函数(Mobius)…305
2.杜教筛…306
(1).map 记忆化…306
(2).数组记忆化…307
3.最值反演 (Min-Max容斥)…308
八、计算几何 …308
∮ 1. 计算几何注意事项…308
1.1 计算误差…309
1.2 解决方案 : 误差判别法…309
1.3 解决方案：化浮为整…309
1.4 注意负零…309
1.5 注意反三角函数的值域…309
1.6 计算几何常用开头模板…309
∮ 2. 注意事项…310
∮ 3. 几何公式…310
1.三角形…311
2.四边形…311
3.正n边形…311
4.圆…311
5.棱柱…311
6.棱锥…312
7.棱台…312
8.圆柱…312
9.圆锥…312
10.圆台…312
11.球…312
12.球台…312
13.球扇形…312
∮ 二维几何基础…313
∮ 1. 基本运算…313
1.1 判断正负函数(sgn)…314
1.2 点积（数量积、内积）(Dot) …314
1.3 向量积，叉积(Cross)…314
1.4 取模（求长度）(Length)…315
1.5 计算两向量夹角(Angle)…315
1.6 计算两向量构成的平行四边形有向面积(Area2) …315
1.7 计算向量逆时针旋转后的向量(Rotate)…315
1.8 计算向量逆时针旋转九十度的单位法线(Normal) …315
1.9 判断折线（向量）bc是不是向（向量）ab的逆时针方向（左边）转向(ToLeftTest) …315
1.10 点绕着 p 点逆时针旋转 angle(rotate)…315
1.11 判断点和直线关系(relation) …316
1.12 复数表示…316
∮ 2. 点与线…316
2.1 直线的实现(Line) …317
2.2 判断点在直线上…317
2.3 计算两直线交点(Get_line_intersection)…317
2.4 计算点到直线的距离(Distance_point_to_line) …317
2.5 计算点到线段的距离(Distance_point_to_segment)…317
2.6 求点在直线上的投影点(Get_line_projection)…317
2.7 判断点是否在线段上(OnSegment) …318
2.8 判断两线段是否相交（不算在端点处相交）(segment_proper_intersection)…318
2.9 判断两线段是否相交（包含端点处相交）(Segment_proper_intersection)…318
2.10 判断点是否在一条线段上(不含端点)(on_segment)…319
2.11 两向量的关系(parallel)…319
2.12 两直线关系(linecrossline) …319
∮ 3. 多边形…319
3.0.三角形…319
3.0.1 三角形四心…320
3.0.2 关键点与A, B, C三顶点距离之和…320
3.0.2.1 费马点…320
3.0.3向量求三角形垂心(getcircle)…320
3.1.0 正多边形的一些性质和概念…321
3.1 求多边形面积(convex_polygon_area) …321
3.2 判断点在多边形内(is_point_in_polygon) …322
3.3 判断点在凸多边形内…322
3.4 求多边形重心(barycenter) …322
3.5 判定凸多边形(is_convex) …323
3.6 判点在凸多边形内或多边形边上(inside_convex)…323
3.7 判点在任意多边形内(inside_polygon)…323
3.8 判线段在任意多边形内(inside_polygon)…323
3.9 多边形切割(常用于半平面交)…325
∮ 4.圆…326
4.1 圆与直线交点(getLineCircleIntersection)…326
4.2 求两圆交点(get_circle_circle_intersection)…327
4.3 点到圆的切线(get_tangents)…327
4.4 两圆的公切线(get_tangents)…328
4.5 两圆相交面积(AreaOfOverlap) …328
4.6 模板合集…329
4.7 判直线和圆相交(intersect_line_circle) …329
4.8 判线段和圆相交(intersect_seg_circle)…329
4.9 判圆和圆相交(intersect_circle_circle)…330
4.10 计算圆上到点p最近点(dot_to_circle) …330
4.11 计算直线/线段与圆的交点（intersection_line_circle）…330
4.12 计算圆与圆的交点（intersection_circle_circle）…330
4.13 求圆外一点对圆的两个切点(TangentPoint_PC) …331
4.14 求三角形的外接圆(get_circumcircle) …331
4.15 求三角形的内接圆(get_incircle)…331
4.16 二维几何110_2合一！…332
4.17 经纬度转换为空间坐标…334
4.18 球面距离…334
4.19 三点确定一圆…334
4.20 两个圆的关系(relationcircle) …335
∮ 5. 网格 …336
5.1 多边形上的网格点个数…336
5.2 多边形内的网格点个数…336
∮ 6.一些函数/定理/应用…336
6.1 欧拉定理…336
6.2 Pick定理（根据点在多边形内和边界的个数求面积）…337
6.3 判断四点共面（混合积）…338
∮ 7. 平面扫描…339
∮ 8. 凸包 …340
8.1 Andrew算法…340
8.2 直线两点式转为一般式使用公式O(1)计算点到直线距离…341
8.3 判断点是否在凸包内…342
∮ 9. 旋转卡壳…342
9.1 求凸包的直径…342
9.2 求两个凸多边形(凸包)间最小距离…344
∮ 10. 半平面交…345
10.1 有向直线…346
10.2 O(nlogn)的半平面交…346
10.3 二分 + 半平面交…347
∮ 11. 闵可夫斯基和…348
∮ 12.平面区域…348
∮ 13.平面最近点对…350
∮ 14. 三维基础操作…353
1.1 三维点积(Dot3)…354
1.2 三维叉积(Cross3) …354
1.3 矢量差（Subt）…355
1.4.1 返回ab，ac，ad的混合积(Volume6) …355
1.4.2 四面体体积(Volume6)…356
1.5 求四面体的重心(Centroid) …356
1.6 凸多面体的重心…356
1.7 二面角…357
∮ 15. 三维点线面 …357
2.1 取平面法向量(NormalVector) …357
2.2 求两点距离(TwoPointDistance)…357
2.3 点p到平面的距离(DistanceToPlane) …358
2.4 点p在平面上的投影(GetPlaneProjection) …358
2.5 直线与平面的交点(LinePlaneIntersection)…358
2.6 空间直线距离(LineToLine)…358
2.7 点到直线的距离(DistanceToLine)…358
2.8 点到线段的距离(DistanceToSeg) …358
2.9 求异面直线与的公垂线对应的s(LineDistance3D)…359
2.10 p1和p2是否在线段a-b的同侧(SameSide)…359
2.11 判断点P是否在三角形中(PointInTri) …359
2.12 三角形P0、P1、P2是否和线段AB相交(TriSegIntersection)…359
2.13 空间两三角形是否相交(TriTriIntersection)…360
2.14 空间两直线上最近点对返回最近距离(SegSegDistance)…360
2.15判断P是否在三角形A, B, C中，并且到三条边的距离都至少
为mindist(InsideWithMinDistance) …360
2.16判断P是否在凸四边形中，并且到四条边的距离都至少为mindist(InsideWithMinDistance) …361
∮ 16. 三维凸包…361
3.1 加干扰防止多点共面(add_noise)…361
3.2 凸包的定义(Face)…362
3.3 增量法求三维凸包(CH3D) …362
3.4 凸多面体(ConvexPolyhedron) …363
3.5 给三维凸包求出重心到各面的最小距离。…364
∮ 17. 最小圆覆盖 …369
∮ 18. 三角剖分(求圆与三角形的公共面积) …370
∮ 19. K次圆覆盖 …372
九、其他 Other…375
∮ 1. 常用函数…375
1.1 全排列：next_permutation …375
1.2 读写优化…375
1.3 返回容器内最大最小值…376
1.4 复制函数…376
1.5 容器删除函数…377
1.6 容器填充函数…377
1.7 查找函数…377
1.8 字符串转换整数 / 数字转字符串…378
1.9 取部分字符串函数…378
∮ 2. 高精度计算 …379
∮ 3. 离散化…380
∮ 4. 基础算法…381
4.1 快速排序…381
4.2 归并排序…382
4.3 整数二分…382
4.4 浮点数二分…382
4.5 高精度加法…383
4.6 高精度减法…383
4.7 高精度乘低精度…383
4.8 高精度除以低精度…384
4.9 一维前缀和 …384
4.10 二维前缀和 …384
4.10.1 二维前缀和求矩阵和…384
4.11 一维差分…385
4.12 二维差分 …385
4.12.1 区间修改使得数列全部相等的最小次数 …385
4.13 双指针算法 …386
4.14 区间合并…386
4.15 龟速乘…386
∮ 5. 表达式求值 …387
5.1 表达式求值（前中后）…387
5.2 递归法求中缀表达式的值，O(n^2) …387
5.3 后缀表达式转中缀表达式，同时求值，O(n)…388
5.4 中缀表达式转后缀表达式，同时对后缀表达式求值 …389
∮ 6. 递归 …389
6.1 奇怪的汉诺塔（n盘m柱）…389
6.2 分形递归…390
lowbit+hash找出二进制下所有1 的位数…391
∮ 7. 二分和三分 …391
7.1 三分法求单峰函数的极值…391
7.2 二分求序列最大平均值…392
∮ 8. 矩阵快速幂 …393
∮ 9. set 和 multiset…394
∮ 10. bitset的用法…395
∮ 11. 进制转换（n进制转m进制） …396
∮ 12. java高精度…396