1 图论 3 1.1 术语 3 1.2 独立集、覆盖集、支配集之间关系 3 1.3 DFS 4 1.3.1 割顶 6 1.3.2 桥 7 1.3.3 强连通分量 7 1.4 最小点基 7 1.5 拓扑排序 7 1.6 欧拉路 8 1.7 哈密顿路（正确？） 9 1.8 Bellman-ford 9 1.9 差分约束系统（用bellman-ford解） 10 1.10 dag最短路径 10 1.11 二分图匹配 11 1.11.1 匈牙利算法 11 1.11.2 KM算法 12 1.12 网络流 15 1.12.1 最大流 15 1.12.2 上下界的网络的最大流 17 1.12.3 上下界的网络的最小流 17 1.12.4 最小费用最大流 18 1.12.5 上下界的网络的最小费用最小流 21 2 数论 21 2.1 最大公约数gcd 21 2.2 最小公倍数lcm 22 2.3 快速幂取模B^LmodP(O(logb)) 22 2.4 Fermat小定理 22 2.5 Rabin-Miller伪素数测试 22 2.6 Pollard-rho 22 2.7 扩展欧几里德算法extended-gcd 24 2.8 欧拉定理 24 2.9 线性同余方程ax≡b(mod n) 24 2.10 中国剩余定理 25 2.11 Discrete Logging(BL == N (mod P)) 26 2.12 N!最后一个不为0的数字 27 2.13 2^14以内的素数 27 3 数据结构 31 3.1 堆（最小堆） 31 3.1.1 删除最小值元素： 31 3.1.2 插入元素和向上调整： 32 3.1.3 堆的建立 32 3.2 并查集 32 3.3 树状数组 33 3.3.1 LOWBIT 33 3.3.2 修改a[p] 33 3.3.3 前缀和A[1]+…+A[p] 34 3.3.4 一个二维树状数组的程序 34 3.4 线段树 35 3.5 字符串 38 3.5.1 字符串哈希 38 3.5.2 KMP算法 40 4 计算几何 41 4.1 直线交点 41 4.2 判断线段相交 41 4.3 三点外接圆圆心 42 4.4 判断点在多边形内 43 4.5 两圆交面积 43 4.6 最小包围圆 44 4.7 经纬度坐标 46 4.8 凸包 46 5 Problem 48 5.1 RMQ-LCA 48 5.1.1 Range Minimum Query(RMQ) 49 5.1.2 Lowest Common Ancestor (LCA) 53 5.1.3 Reduction from LCA to RMQ 56 5.1.4 From RMQ to LCA 57 5.1.5 An algorithm for the restricted RMQ 60 5.1.6 An AC programme 61 5.2 最长公共子序列LCS 64 5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67 5.5 0/1背包问题 68 6 组合数学相关 69 6.1 The Number of the Same BST 69 6.2 排列生成 71 6.3 逆序 72 6.3.1 归并排序求逆序 72 7 数值分析 72 7.1 二分法 72 7.2 迭代法(x=f(x)) 73 7.3 牛顿迭代 74 7.4 数值积分 74 7.5 高斯消元 75 8 其它 77

各种算法模板，吉大，交大，中山，浙大等各高校模板

ACM模板，主要包括图论，字符串，数据结构等模板，例如 图论 1.1 网络流 1.1.1 最大流 1.1.1.1 算法模板 1.1.1.2 二分图匹配 1.1.1.3 上下界可行流 1.1.1.4 多源汇最大流 1.1.1.5 关键边 1.1.1.6 最大流判定 1.1.1.7 拆点 1.1.1.8 建图实战 1.1.2 最小割 1.1.2.1 算法模板 1.1.2.2 直接应用 1.1.2.3 最大权闭合图 1.1.2.4 最大密度子图 1.1.2.5 最小点权覆盖集 1.1.2.6 最大点权独立集 1.1.2.7 建图实战 1.1.3 费用流 1.1.3.1 算法模板 等

内容包括搜索回溯分治、计算几何、动态规划、背包问题求解、线段树典型求解问题、字典树、图论、差分约束系统、贪心等，适用于大学生ACM竞赛赛前准备训练

acm模板总汇.pdf

杭电ACM模板，热爱的人可以看看，一点会有很多的收获的

C/C++的ACM模板 包括各种数据结构算法 DP算法，搜索算法，STL算法，博弈算法，图论

目录 目录 .............................................. 1 Graph 图论 ........................................ 3 | DAG的深度优先搜索标记 ............................................. 3 | 无向图找桥 ..................................................................... 3 | 无向图连通度(割) ........................................................ 3 | 大团问题 DP + DFS ................................................. 3 | 欧拉路径O(E) ............................................................... 3 | DIJKSTRA数组实现O（N^2） ..................................... 3 | DIJKSTRA O(E * LOG E) ............................................. 4 | BELLMANFORD单源短路O(VE) ................................. 4 | SPFA(SHORTEST PATH FASTER ALGORITHM) .............. 4 | 第K短路（DIJKSTRA） ................................................. 5 | 第K短路（A*） ............................................................ 5

ACM Fighting! 2 1.计算几何 5 1.1 注意 5 1.2几何公式 6 1.3 多边形 8 1.4多边形切割 11 1.5 浮点函数 12 1.6 面积 18 1.7球面 18 1.8三角形 19 1.9三维几何 22 1.10 凸包 30 1.11 网格 32 1.12 圆 33 1.13 矢量运算求几何模板 35 1.14结构体表示几何图形 47 1.15四城部分几何模板 52 1.16 一些代码 54 1.16.1 最小圆覆盖_zju1450 54 1.16.2 直线旋转_两凸包的最短距离(poj3608) 58 1.16.3 扇形的重心 62 1.16.4 根据经度纬度求球面距离 62 1.16.5 多边形的重心 64 1.16.6 存不存在一个平面把两堆点分开(poj3643) 66 1.16.7 pku_3335_判断多边形的核是否存在 67 1.16.8 pku_2600_二分+圆的参数方程 74 1.16.9 pku_1151_矩形相交的面积 76 1.16.10 pku_1118_共线最多的点的个数 78 1.16.11 pku2826_线段围成的区域可储水量 80 1.16.12 Pick公式 84 1.16.13 N点中三个点组成三角形面积最大 86 1.16.14 直线关于圆的反射 89 1.16.15 pku2002_3432_N个点最多组成多少个正方形(hao) 94 1.16.16 pku1981_单位圆覆盖最多点(poj1981)CircleandPoints 97 1.16.17 pku3668_GameofLine_N个点最多确定多少互不平行的直线(poj3668) 99 1.16.18 求凸多边形直径 100 2.组合 102 2.1 组合公式 102 2.2 排列组合生成 102 2.3 生成gray码 104 2.4 置换(polya) 104 2.5 字典序全排列 105 2.6 字典序组合 105 2.7 一些原理及其例子 106 3.数论 108 3.1 阶乘最后非0位 108 3.2 模线性方程组 108 3.3 素数 110 3.4 欧拉函数 114 3.6高精度 116 3.6.1平方根 116 3.6.2 高精度乘幂 117 3.7 高斯消元回代法 122 3.8 数值计算 124 3.8.1 定积分计算 124 3.8.2 多项式求根(牛顿法) 125 3.8.3 周期性方程(追赶法) 127 4.排序 128 4.1快速选择算法 128 4.2归并排序+逆序数的求取 128 5.字符串 130 5.1 KMP应用 130 5.2 后缀数组 131 5.3 中缀表达式转后缀表达式 134 5.4 Firefighters 表达式求值 135 6.博弈 139 6.1 博弈的AB剪枝 139 6.1.1 取石子 139 6.2 博弈 SG函数 局势分割 141 7.数据结构 142 7.1 TRIE 142 7.2 线段树 147 7.3 并查集 151 7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割和桥 171 8.8 最小生成树(kruskal) 172 8.9 最短路径 173 8.10 最大网络流 175 8.11 最小费用流 180 8.12 最大团问题 182 8.13 二分图匹配 184 8.14 带权的最优二分图匹配 184 9.搜索算法概略 187 9.1 迭代深搜+IDA* 187 9.2 分之界限法（深搜） 189 9.3 A* 8数码问题( pascal ) 192 9.4 优先队列广搜 194 10.应用 197 10.1 Joseph问题 197 10.2 N皇后构造解 197 10.3 布尔母函数 198 10.4 第k元素 199 10.5 幻方构造 199 10.6 模式匹配(kmp) 201 10.7 逆序对数 201 10.8 字符串最小表示 202 10.9 最长公共单调子序列 202 10.10 最长子序列 204 10.11 最大子串匹配 204 10.12 最大子段和 205 10.13 最大子阵和 206 11.其它 207 11.1 大数(只能处理正数) 207 11.2 分数 212 11.3 矩阵 214 11.4 线性方程组 216 11. 5 线性相关 218 11.6 日期 219 11.7 读入 220 11.8 函数 220

⼤数、⼆分、枚举排列、⼦集⽣成、n皇后回溯、并查集、树状数组、KMP，unday，BM、01背包，完全背包、最⻓(不)上升或下降⼦序列、最⻓公共⼦序列、拓扑排序。。。。 欧拉路径和回路 搜索 最⼩⽣成树 最短路 GCD和LCM 埃拉托斯特尼筛法 唯⼀分定理 扩展欧⼏⾥得 欧拉函数 快速幂 矩阵快速幂