首页 > 全部内容 > 编程书籍 > 常用算法代码.pdf
2019
01-30

常用算法代码.pdf

下载地址

ACM/ICPC 算法代码库,供日常使用参考。

目录 ………………………………………. 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

| PRIM 求MST ………………………………………………………….. 6

| 次小生成树O(V^2) ……………………………………………… 6

| 最小生成森林问题(K 颗树)O(MLOGM). …………………. 6

| 有向图最小树形图 ………………………………………………… 6

| MINIMAL STEINER TREE ………………………………………… 6

| TARJAN 强连通分量 ……………………………………………….. 7

| 弦图判断 ………………………………………………………………. 7

| 弦图的PERFECT ELIMINATION 点排列 …………………….. 7

| 稳定婚姻问题 O(N^2) ………………………………………….. 7

| 拓扑排序 ………………………………………………………………. 8

| 无向图连通分支(DFS/BFS 邻接阵) ……………………….. 8

| 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) ………… 8

| 有向图最小点基(邻接阵)O(N^2)…………………………. 9

| FLOYD 求最小环 …………………………………………………….. 9

| 2-SAT 问题 …………………………………………………………… 9

Network 网络流 …………………………….. 11

| 二分图匹配(匈牙利算法DFS 实现) …………………. 11

| 二分图匹配(匈牙利算法BFS 实现) …………………. 11

| 二分图匹配(HOPCROFT-CARP 的算法) ……………… 11

| 二分图最佳匹配(KUHN MUNKRAS 算法O(M*M*N)) 11

| 无向图最小割 O(N^3) ……………………………………….. 12

| 有上下界的最小(最大)流 …………………………………… 12

| DINIC 最大流 O(V^2 * E) ………………………………… 12

| HLPP 最大流 O(V^3) ………………………………………… 13

| 最小费用流 O(V * E * F) ………………………………… 13

| 最小费用流 O(V^2 * F) ……………………………………. 14

| 最佳边割集 …………………………………………………………. 15

| 最佳点割集 …………………………………………………………. 15

| 最小边割集 …………………………………………………………. 15

| 最小点割集(点连通度) ……………………………………. 16

| 最小路径覆盖O(N^3) ………………………………………… 16

| 最小点集覆盖 ……………………………………………………… 16

Structure 数据结构 …………………………. 17

| 求某天是星期几 ………………………………………………….. 17

| 左偏树 合并复杂度O(LOG N) …………………………….. 17

| 树状数组 …………………………………………………………….. 17

| 二维树状数组 ……………………………………………………… 17

| TRIE 树(K 叉) …………………………………………………….. 17

| TRIE 树(左儿子又兄弟) ……………………………………… 18

| 后缀数组 O(N * LOG N) …………………………………….. 18

| 后缀数组 O(N) …………………………………………………… 18

| RMQ 离线算法 O(N*LOGN)+O(1) ……………………….. 19

| RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法

(O(NLOGN + Q)) ……………………………………………………. 19

| RMQ 离线算法 O(N*LOGN)+O(1)求解LCA …………. 19

| LCA 离线算法 O(E)+O(1) …………………………………. 20

| 带权值的并查集 ………………………………………………….. 20

| 快速排序 …………………………………………………………….. 20

| 2 台机器工作调度 ……………………………………………….. 20

| 比较高效的大数 ………………………………………………….. 20

| 普通的大数运算 ………………………………………………….. 21

| 最长公共递增子序列 O(N^2) ……………………………… 22

| 0-1 分数规划 ……………………………………………………… 22

| 最长有序子序列(递增/递减/非递增/非递减) …. 22

| 最长公共子序列 ………………………………………………….. 23

| 最少找硬币问题(贪心策略-深搜实现) …………….. 23

| 棋盘分割 …………………………………………………………….. 23

| 汉诺塔 ………………………………………………………………… 23

| STL 中的PRIORITY_QUEUE …………………………………… 24

| 堆栈 ……………………………………………………………………. 24

| 区间最大频率 ……………………………………………………… 24

| 取第K 个元素………………………………………………………. 25

| 归并排序求逆序数 ………………………………………………. 25

| 逆序数推排列数 ………………………………………………….. 25

| 二分查找 …………………………………………………………….. 25

| 二分查找(大于等于V 的第一个值)…………………… 25

| 所有数位相加 ……………………………………………………… 25

Number 数论 ……………………………….. 26

2

|递推求欧拉函数PHI(I) ……………………………………….. 26

|单独求欧拉函数PHI(X) ……………………………………….. 26

| GCD 最大公约数 …………………………………………………. 26

| 快速 GCD ……………………………………………………………. 26

| 扩展 GCD ……………………………………………………………. 26

| 模线性方程 A * X = B (% N) ……………………………. 26

| 模线性方程组 ……………………………………………………… 26

| 筛素数 [1..N] …………………………………………………… 26

| 高效求小范围素数 [1..N] …………………………………. 26

| 随机素数测试(伪素数原理) ……………………………….. 26

| 组合数学相关 ……………………………………………………… 26

| POLYA 计数 ………………………………………………………….. 27

| 组合数C(N, R) ………………………………………………….. 27

| 最大1 矩阵 …………………………………………………………. 27

| 约瑟夫环问题(数学方法) ………………………………… 27

| 约瑟夫环问题(数组模拟) ………………………………… 27

| 取石子游戏1 ………………………………………………………. 27

| 集合划分问题 ……………………………………………………… 27

| 大数平方根(字符串数组表示) …………………………. 28

| 大数取模的二进制方法 ……………………………………….. 28

| 线性方程组A[][]X[]=B[] ………………………………… 28

| 追赶法解周期性方程 …………………………………………… 28

| 阶乘最后非零位,复杂度O(NLOGN) ……………………… 29

递归方法求解排列组合问题 ……………………. 30

| 类循环排列 …………………………………………………………. 30

| 全排列 ………………………………………………………………… 30

| 不重复排列 …………………………………………………………. 30

| 全组合 ………………………………………………………………… 31

| 不重复组合 …………………………………………………………. 31

| 应用 ……………………………………………………………………. 31

模式串匹配问题总结 …………………………. 32

| 字符串HASH ………………………………………………………… 32

| KMP 匹配算法O(M+N) ……………………………………….. 32

| KARP-RABIN 字符串匹配 ……………………………………… 32

| 基于KARP-RABIN 的字符块匹配…………………………… 32

| 函数名: STRSTR ………………………………………………….. 32

| BM 算法的改进的算法SUNDAY ALGORITHM ……………. 32

| 最短公共祖先(两个长字符串) …………………………. 33

| 最短公共祖先(多个短字符串) …………………………. 33

Geometry 计算几何 ………………………….. 34

| GRAHAM 求凸包 O(N * LOGN) ……………………………… 34

| 判断线段相交 ……………………………………………………… 34

| 求多边形重心 ……………………………………………………… 34

| 三角形几个重要的点 …………………………………………… 34

| 平面最近点对 O(N * LOGN) ……………………………….. 34

| LIUCTIC 的计算几何库 ………………………………………… 35

| 求平面上两点之间的距离 ……………………………………. 35

| (P1-P0)*(P2-P0)的叉积 ………………………………… 35

| 确定两条线段是否相交 ……………………………………….. 35

| 判断点P 是否在线段L 上 …………………………………….. 35

| 判断两个点是否相等 …………………………………………… 35

| 线段相交判断函数 ………………………………………………. 35

| 判断点Q 是否在多边形内 …………………………………… 35

| 计算多边形的面积 ………………………………………………. 35

| 解二次方程 AX^2+BX+C=0 …………………………………. 36

| 计算直线的一般式 AX+BY+C=0 …………………………… 36

| 点到直线距离 ……………………………………………………… 36

| 直线与圆的交点,已知直线与圆相交 ………………….. 36

| 点是否在射线的正向 …………………………………………… 36

| 射线与圆的第一个交点 ……………………………………….. 36

| 求点P1 关于直线LN 的对称点P2 ………………………… 36

| 两直线夹角(弧度) …………………………………………… 36

ACM/ICPC 竞赛之STL …………………………. 37

ACM/ICPC 竞赛之STL 简介 …………………………………… 37

ACM/ICPC 竞赛之STL–PAIR ……………………………….. 37

ACM/ICPC 竞赛之STL–VECTOR ……………………………. 37

ACM/ICPC 竞赛之STL–ITERATOR 简介 …………………. 38

ACM/ICPC 竞赛之STL–STRING ……………………………. 38

ACM/ICPC 竞赛之STL–STACK/QUEUE …………………… 38

ACM/ICPC 竞赛之STL–MAP …………………………………. 40

ACM/ICPC 竞赛之STL–ALGORITHM ……………………….. 40

STL IN ACM …………………………………………………………… 41

头文件 ……………………………………………………………………. 42

线段树 ……………………………………. 43

求矩形并的面积(线段树+离散化+扫描线) …………… 43

求矩形并的周长(线段树+离散化+扫描线) …………… 44

最后编辑:
作者:Null
这个作者貌似有点懒,什么都没有留下。