ACM常用算法代码 pdf

目录 一．数论 4 1.阶乘最后非零位 4 2. 模线性方程(组) 4 3. 素数表 6 4. 素数随机判定(miller_rabin) 6 5. 质因数分解 7 6. 最大公约数欧拉函数 8 二．图论_匹配 9 1. 二分图最大匹配(hungary邻接表形式) 9 2. 二分图最大匹配(hungary邻接表形式,邻接阵接口) 10 3. 二分图最大匹配(hungary邻接阵形式) 10 4. 二分图最大匹配(hungary正向表形式) 11 5. 二分图最佳匹配(kuhn_munkras邻接阵形式) 11 6. 一般图匹配(邻接表形式) 12 7. 一般图匹配(邻接表形式,邻接阵接口) 13 8. 一般图匹配(邻接阵形式) 14 9. 一般图匹配(正向表形式) 15 三．图论_生成树 16 1. 最小生成树(kruskal邻接表形式) 16 2. 最小生成树(kruskal正向表形式) 17 3. 最小生成树(prim+binary_heap邻接表形式) 19 4. 最小生成树(prim+binary_heap正向表形式) 20 5. 最小生成树(prim+mapped_heap邻接表形式) 21 6. 最小生成树(prim+mapped_heap正向表形式) 22 7. 最小生成树(prim邻接阵形式) 23 8. 最小树形图(邻接阵形式) 24 四．图论_网络流 25 1. 上下界最大流(邻接表形式) 25 2. 上下界最大流(邻接阵形式) 26 3. 上下界最小流(邻接表形式) 27 4. 上下界最小流(邻接阵形式) 29 5. 最大流(邻接表形式) 30 6. 最大流(邻接表形式,邻接阵接口) 31 7. 最大流(邻接阵形式) 32 8. 最大流无流量(邻接阵形式) 32 9. 最小费用最大流(邻接阵形式) 33 五. 图论_最短路径 34 1. 最短路径(单源bellman_ford邻接阵形式) 34 2. 最短路径(单源dijkstra_bfs邻接表形式) 35 3. 最短路径(单源dijkstra_bfs正向表形式) 35 4. 最短路径(单源dijkstra+binary_heap邻接表形式) 36 5. 最短路径(单源dijkstra+binary_heap正向表形式) 37 6. 最短路径(单源dijkstra+mapped_heap邻接表形式) 38 7. 最短路径(单源dijkstra+mapped_heap正向表形式) 39 8. 最短路径(单源dijkstra邻接阵形式) 40 9. 最短路径(多源floyd_warshall邻接阵形式) 40 六. 图论_连通性 41 1. 无向图关键边(dfs邻接阵形式) 41 2. 无向图关键点(dfs邻接阵形式) 42 3. 无向图块(bfs邻接阵形式) 43 4. 无向图连通分支(bfs邻接阵形式) 43 5. 无向图连通分支(dfs邻接阵形式) 44 6. 有向图强连通分支(bfs邻接阵形式) 44 7. 有向图强连通分支(dfs邻接阵形式) 45 8. 有向图最小点基(邻接阵形式) 46 七. 图论_应用 46 1.欧拉回路(邻接阵形式) 46 2. 前序表转化 47 3. 树的优化算法 48 4. 拓扑排序(邻接阵形式). 49 5. 最佳边割集 50 6. 最佳顶点割集 51 7. 最小边割集 52 8. 最小顶点割集 53 9. 最小路径覆盖 55 八. 图论_NP搜索 55 1. 最大团(n小于64)(faster) 55 2. 最大团 58 九. 组合 59 1. 排列组合生成 59 2. 生成gray码 60 3. 置换(polya) 61 4. 字典序全排列 61 5. 字典序组合 62 6. 组合公式 62 十. 数值计算 63 1. 定积分计算(Romberg) 63 2. 多项式求根(牛顿法) 64 3. 周期性方程(追赶法) 66 十一. 几何 67 1. 多边形 67 2. 多边形切割 70 3. 浮点函数 71 4. 几何公式 76 5. 面积 78 6. 球面 79 7. 三角形 79 8. 三维几何 81 9. 凸包(graham) 89 10. 网格(pick) 91 11. 圆 92 12. 整数函数 94 13. 注意 96 十二. 结构 97 1. 并查集 97 2. 并查集扩展(friend_enemy) 98 3. 堆(binary) 98 4. 堆(mapped) 99 5. 矩形切割 99 6. 线段树 100 7. 线段树扩展 102 8. 线段树应用 105 9. 子段和 105 10. 子阵和 105 十三. 其他 106 1. 分数 106 2. 矩阵 108 3. 日期 110 4. 线性方程组(gauss) 111 5. 线性相关 113 十四. 应用 114 1. joseph 114 2. N皇后构造解 115 3. 布尔母函数 115 4. 第k元素 116 5. 幻方构造 116 6. 模式匹配(kmp) 118 7. 逆序对数 118 8. 字符串最小表示 119 9. 最长公共单调子序列 119 10. 最长子序列 120 11. 最大子串匹配 121 12. 最大子段和 122 13. 最大子阵和 123 ### ACM常用算法代码知识点概述 #### 一、数论 **1. 阶乘最后非零位** - **定义**: 计算一个数的阶乘后结果的末尾第一个非零数字。 - **应用场景**: 在数学问题或编程竞赛中需要处理阶乘问题时，特别是当阶乘值非常大无法直接计算时。 - **实现思路**: 通过分析10的因子（即2和5）在阶乘中的分布情况来确定最后非零位。 **2. 模线性方程(组)** - **定义**: 解决形如\(ax \equiv b \pmod{m}\)的方程，其中\(a\)、\(b\)、\(m\)为已知整数。 - **应用场景**: 加密算法、密码学等领域。 - **实现方法**: 可以通过扩展欧几里得算法求解。 **3. 素数表** - **定义**: 列出一定范围内所有的素数。 - **应用场景**: 计算机科学中的加密技术、哈希函数等。 - **实现方法**: 使用埃拉托斯特尼筛法生成。 **4. 素数随机判定(Miller-Rabin)** - **定义**: Miller-Rabin测试是一种用于确定一个给定整数是否为素数的概率性算法。 - **应用场景**: 当需要快速判断大整数是否为素数时。 - **实现方法**: 基于费马小定理的扩展，通过随机选取测试基数来进行多次测试。 **5. 质因数分解** - **定义**: 将一个合数表示为多个质数相乘的形式。 - **应用场景**: 密码学中的RSA加密算法依赖于此。 - **实现方法**: 试除法是最简单的方法；对于较大数字可以采用更高效的算法，如Pollard’s rho算法。 **6. 最大公约数与欧拉函数** - **定义**: 最大公约数(GCD)指两个或多个整数共有的最大的正整数约数；欧拉函数\(φ(n)\)是小于等于\(n\)的正整数中与\(n\)互质的数的数量。 - **应用场景**: 数论研究及各种算法设计。 - **实现方法**: GCD可以通过辗转相除法实现；欧拉函数可以通过质因数分解来计算。 #### 二、图论_匹配 **1. 二分图最大匹配(Hungary邻接表/邻接阵/正向表形式)** - **定义**: 在二分图中寻找最大的匹配集合。 - **应用场景**: 匹配问题，例如工作分配问题。 - **实现方法**: Hungary算法通过构建增广路径来不断改进匹配。 **2. 二分图最佳匹配(Kuhn-Munkras邻接阵形式)** - **定义**: 找到二分图中所有匹配中代价最小的一个。 - **应用场景**: 适用于带有权值的匹配问题。 - **实现方法**: Kuhn-Munkras算法基于Hungary算法进行改进。 **3. 一般图匹配(邻接表/邻接阵/正向表形式)** - **定义**: 在任意图中寻找最大匹配。 - **应用场景**: 同上。 - **实现方法**: 对于一般图的匹配问题，通常采用类似Hungary算法的方法，但需要考虑更多的情况。 #### 三、图论_生成树 **1. 最小生成树(Kruskal/Prim邻接表/正向表形式)** - **定义**: 给定一个带权重的无向图，找到一棵包含所有顶点且总权重最小的树。 - **应用场景**: 网络设计问题。 - **实现方法**: Kruskal算法按边的权重从小到大依次加入不构成环的边；Prim算法从任意顶点出发，逐步将最近的未连接顶点加入。 **2. 最小树形图(邻接阵形式)** - **定义**: 给定一个带权重的有向图，找到一个包含所有顶点的树形图，使得树中所有边的权重之和最小。 - **应用场景**: 适用于有向图的最小成本路径问题。 - **实现方法**: 类似于最小生成树算法，但是需要处理有向边的情况。 #### 四、图论_网络流 **1. 上下界最大流/最小流(邻接表/邻接阵形式)** - **定义**: 在网络流中找到满足流量限制条件下的最大/最小流量。 - **应用场景**: 资源分配问题。 - **实现方法**: 增广路径算法。 **2. 最大流(邻接表/邻接阵形式)** - **定义**: 在网络流中找到最大可能的流量。 - **应用场景**: 网络传输问题。 - **实现方法**: Ford-Fulkerson算法通过反复寻找增广路径来提高流量。 **3. 最小费用最大流(邻接阵形式)** - **定义**: 在满足最大流量的情况下，找到最小的总费用。 - **应用场景**: 运输问题、供应链管理等。 - **实现方法**: 可以通过Dijkstra算法或Bellman-Ford算法结合增广路径法实现。 #### 五、图论_最短路径 **1. 最短路径(单源/多源Bellman-Ford/Dijkstra邻接表/正向表/邻接阵形式)** - **定义**: 在图中找到从一个顶点到其他所有顶点的最短路径。 - **应用场景**: 导航系统、通信网络等。 - **实现方法**: Dijkstra算法适用于没有负权重边的情况；Bellman-Ford算法则适用于存在负权重边的情况。 **2. 最短路径(Floyd-Warshall邻接阵形式)** - **定义**: 找到图中所有顶点之间的最短路径。 - **应用场景**: 在规划路径或交通网络中。 - **实现方法**: Floyd-Warshall算法通过动态规划的方式逐层递推。 #### 六、图论_连通性 **1. 无向图/有向图关键边/点/块/连通分支(邻接阵形式)** - **定义**: 找出图中的关键组件，如关键边、关键点等。 - **应用场景**: 网络可靠性分析、社交网络分析等。 - **实现方法**: 深度优先搜索(DFS)和广度优先搜索(BFS)可用于识别这些组件。 #### 七、图论_应用 **1. 欧拉回路(邻接阵形式)** - **定义**: 找到一条经过每条边恰好一次的回路。 - **应用场景**: 旅行商问题(TSP)的变体。 - **实现方法**: 需要确保图中的每个顶点的度数都是偶数，并且至少有两个奇数度的顶点。 **2. 前序表转化/拓扑排序(邻接阵形式)** - **定义**: 将前序表转化为后序表或者进行拓扑排序。 - **应用场景**: 数据库查询优化、编译器设计等。 - **实现方法**: 使用栈数据结构辅助完成转化。 **3. 最佳边/顶点割集** - **定义**: 找到一组边或顶点，删除它们后可以将图分割成多个独立部分。 - **应用场景**: 图的分区问题。 - **实现方法**: 可以通过广度优先搜索(BFS)或深度优先搜索(DFS)来实现。 **4. 最小路径覆盖** - **定义**: 找到覆盖图中所有顶点所需的最少路径数量。 - **应用场景**: 任务调度问题。 - **实现方法**: 使用匈牙利算法或其他匹配算法为基础。 #### 八、图论_NP搜索 **1. 最大团(N小于64)(Faster)** - **定义**: 找到图中最大的完全子图。 - **应用场景**: 社交网络分析。 - **实现方法**: 对于小规模图可以采用穷举法。 #### 九、组合 **1. 排列组合生成/生成Gray码/置换(Polya)/字典序全排列/组合** - **定义**: 生成特定类型的排列或组合。 - **应用场景**: 在密码学、信息安全等领域。 - **实现方法**: 递归法、迭代法等。 **2. 组合公式** - **定义**: 计算组合数\(C(n, k)\)。 - **应用场景**: 概率论和统计学中的计算。 - **实现方法**: 直接使用组合数公式计算。 #### 十、数值计算 **1. 定积分计算(Romberg)** - **定义**: 使用Romberg方法近似计算定积分。 - **应用场景**: 数值分析、工程计算。 - **实现方法**: Romberg积分法是一种加速梯形法则的方法。 **2. 多项式求根(牛顿法)** - **定义**: 使用牛顿法求解多项式的根。 - **应用场景**: 数值分析、物理模拟等。 - **实现方法**: 牛顿法通过迭代逐步逼近根的位置。 **3. 周期性方程(追赶法)** - **定义**: 求解周期性的线性方程组。 - **应用场景**: 数值分析中的特殊类型问题。 - **实现方法**: 通过追赶算法逐步求解。 #### 十一、几何 **1. 多边形/多边形切割/浮点函数/几何公式/面积/球面/三角形/三维几何/凸包(Graham)/网格(Pick)/圆/整数函数** - **定义**: 包括多边形的属性、计算方法以及相关的几何图形处理。 - **应用场景**: CAD软件开发、图形用户界面设计等。 - **实现方法**: 几何计算方法包括面积公式、向量运算、距离计算等。 #### 十二、结构 **1. 并查集/并查集扩展(Friend_Enemy)/堆(Binary/Mapped)/矩形切割/线段树/线段树扩展/线段树应用/子段和/子阵和** - **定义**: 实现特定的数据结构及其应用。 - **应用场景**: 数据存储与检索、算法优化等。 - **实现方法**: 数据结构的设计与实现，例如并查集用于处理不相交集合的问题。 #### 十三、其他 **1. 分数/矩阵/日期/线性方程组(Gauss)/线性相关** - **定义**: 包括分数操作、矩阵运算、日期处理、线性方程组求解等内容。 - **应用场景**: 数学计算、数据分析等。 - **实现方法**: 分数和矩阵的操作通常涉及基础数学算法；线性方程组求解可以使用高斯消元法。 #### 十四、应用 **1. Joseph/N皇后构造解/布尔母函数/第K元素/幻方构造/模式匹配(KMP)/逆序对数/字符串最小表示/最长公共单调子序列/最长子序列/最大子串匹配/最大子段和/最大子阵和** - **定义**: 包括各种实际问题的算法解决方案。 - **应用场景**: 数据处理、模式识别等。 - **实现方法**: 通过特定的算法或数据结构来解决具体问题，如Joseph问题可以使用循环队列模拟。