ACM_TEMPLATE

ACM模板

感谢 南京大学本科中科院软件所硕士 退役ACMer、大佬 “发神” 王宪发学长提供的模板。

本模板在大佬模板的基础上有大量的增加和改动，以适应自己的需要。

测过的模板目录：

代码模板

• 我的代码模板

• 发神的代码模板

高精度模板

• C++大数类（加减乘除取模）

• Java高精度与字符串

字符串算法

• KMP算法

  • KMP

  • KMP最大表示法

  • KMP最小表示法

• Manacher算法

• Trie字典树

• AC自动机

数据结构

• 并查集（单点修改、撤销）

• 线段树

  • 线段树（数组版）
  • 线段树（结构体版）

• 树状数组

• 二维树状数组

• ST表

• 树链剖分（我竟然还学过这个东西？？？）

图论

• 最小生成树

  • Prim算法
  • Kruskal算法

• 最短路

  • Dijkstra算法（堆优化）
  • Floyd算法
  • SPFA算法
  • 差分约束

• 无向图

  • 无向图的割点与桥（Tarjan算法）
  • 点-双连通分量
  • 点-双连通分量
  • 点连通度与边连通度

• 有向图

  • 有向图判环（DFS染色法）
  • 有向图强联通分量（Tarjan算法）

• 二分图

  • 判定二分图（染色法）
  • 二分图最大匹配匈牙利算法（DFS版）
  • 二分图最大匹配匈牙利算法（BFS版）
  • 二分图最大匹配Hopcroft-Karp算法
  • 二分图完美匹配KM算法

• LCA

  • LCA在线算法（倍增）
  • LCA离线算法（Tarjan算法）

• 最小树形图朱刘算法

• 全局最小割Stoer_Wagner算法

• 2-SAT

网络流

• 最大流

  • Dinic算法
  • SAP
  • 上下界网络流
  • 最少最小割边数

• 最小费用最大流

  • MCMF
  • zkw费用流

• 最大权闭合子图

数学

• 数论

  • FFT（快速傅里叶变换）
  • Miller_Robin素性测试+Pollard_rho大数因数分解
  • 埃氏筛求反素数（线性筛求反素数）
  • 欧拉函数
  • 快速幂
  • 矩阵快速幂
  • 辗转相除法（欧几里得算法）
  • 扩展欧几里得算法
  • 求逆元

• 线性代数

  • 高斯消元法（整数）
  • 高斯消元法（浮点数）
  • 高斯消元法（异或）

• 组合数学

  • 求组合数

计算几何

计算几何模板详细目录

• A. 点、向量、直线与线段相关算法

• B. 圆相关算法

• C. 多边形和凸包相关算法

• D. 旋转卡壳

• E. 半平面交

• F. 平面直线图

小算法（杂项）

• Dancing Link（舞蹈链算法）

  • DLX 精确覆盖
  • DLX 重复覆盖
  • DLX 解数独问题

• dfs序

• 二分查找

• 三分查找

• 启发式搜索A*算法

• 动态规划（dp）

  • 背包问题
  • 最长上升子序列（LIS）
  • 数位dp（数位统计）
  • 树的重心（树形dp）
  • 树的直径（两次dfs+树形dp）

• 线性筛法

• 线性预处理逆元

• 莫队算法（我好像没有学过这个东西却莫名的会用这个模板？？？）

未测过（即将测试）的模板目录：

• 斜率dp
• 莫队算法（补学一下并更新一下模板）