### ACM算法模板（吉林大学）
#### 知识点概述
本文档主要涵盖了计算机科学领域内常用的ACM/ICPC竞赛中的算法模板，包括但不限于图论、网络流、数据结构、数论以及模式串匹配和计算几何等多个方面。文档旨在为吉林大学计算机科学与技术学院的学生提供一个全面且实用的算法学习资源。
#### 图论（Graph Theory）
1. **DAG的深度优先搜索标记**
- DAG（有向无环图）是一种特殊的图，没有回路的存在使得在处理时可以采用更高效的算法。
- 深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法，通过标记节点来避免重复访问同一节点。
2. **无向图找桥**
- 在无向图中寻找连接两个不同部分的唯一边，即“桥”，对于分析图的连通性和冗余路径具有重要意义。
3. **无向图连通度（割）**
- 连通度衡量的是图的连通性，割则指去除特定数量的顶点或边后，图被分为两个或多个互不连通的部分。
4. **最大团问题DP+DFS**
- 最大团问题是指在一个图中找到最大的完全子图。通常通过动态规划结合深度优先搜索来解决。
5. **欧拉路径O(E)**
- 欧拉路径是在一个图中经过每条边恰好一次的路径。该算法复杂度为O(E)，其中E为边的数量。
6. **DIJKSTRA算法**
- DIJKSTRA算法用于寻找图中两点之间的最短路径。
- 数组实现：时间复杂度为O(N^2)。
- 使用优先队列实现：时间复杂度为O(E*logE)。
7. **BELLMAN-FORD单源最短路O(VE)**
- BELLMAN-FORD算法可用于检测负权边，适用于存在负权边的情况，时间复杂度为O(VE)。
8. **SPFA (SHORTEST PATH FASTER ALGORITHM)**
- SPFA是一种优化了的贝尔曼-福特算法，能够更高效地处理稀疏图中的单源最短路径问题。
9. **第K短路**
- 第K短路问题涉及寻找两个节点之间第K条最短路径，可以通过修改DIJKSTRA算法或A*算法实现。
10. **PRIM求MST**
- PRIM算法用于寻找最小生成树（MST），通过迭代选择最小权重的边加入树中直到包含所有节点为止。
11. **次小生成树O(V^2)**
- 次小生成树问题是指在所有可能的最小生成树中寻找次优解。
12. **最小生成森林问题(K颗树)O(MlogM)**
- 最小生成森林问题涉及在图中寻找K棵最小生成树。
13. **有向图最小树形图**
- 有向图的最小树形图是指从某个顶点出发，通过一系列边到达其他所有顶点的最短路径的集合。
14. **TARJAN强连通分量**
- TARJAN算法是一种高效的寻找强连通分量的方法，利用深度优先搜索进行。
15. **弦图判断**
- 弦图是一种特殊的图，每个简单环至少含有一个弦。判断一个图是否为弦图有助于简化一些算法。
16. **稳定婚姻问题O(N^2)**
- 稳定婚姻问题涉及为两组人匹配配偶，确保没有一对未配对的人愿意互相配对。
17. **拓扑排序**
- 拓扑排序是对有向无环图的一种排序方式，按照依赖关系对节点进行排序。
18. **无向图连通分支(DFS/BFS邻接阵)**
- 连通分支指的是无向图中相互连通的所有顶点的集合。
19. **有向图强连通分支(DFS/BFS邻接阵)O(N^2)**
- 强连通分支是指图中任意两个顶点都可通过有向边互达的顶点集合。
20. **有向图最小点基(邻接阵)O(N^2)**
- 最小点基是指在有向图中移除这些点后，图变得不再强连通。
21. **FLOYD求最小环**
- FLOYD算法可用来寻找图中任意两点间的最短路径，同时也可以用于求解最小环。
22. **2-SAT问题**
- 2-SAT问题是指在布尔表达式中，每一条子句只包含两个变量，求解是否存在一个满足该公式的赋值。
#### 网络流（Network Flow）
1. **二分图匹配**
- 匈牙利算法（DFS/BFS实现）、HOPCROFT-CARP算法、KUHNMUNKRAS算法等都是用于解决二分图匹配的经典算法。
2. **无向图最小割O(N^3)**
- 最小割是指从源点到汇点的最小流量，通常用于分析网络的最大流量。
3. **有上下界的最小(最大)流**
- 当流量限制不仅包括容量上限，还可能有下限时，需要使用更复杂的算法。
4. **DINIC最大流O(V^2*E)**
- DINIC算法是一种高效的求解最大流的方法，适合处理大规模网络流问题。
5. **HLPP最大流O(V^3)**
- HLPP算法也是另一种高效的求解最大流的方法。
6. **最小费用流**
- 最小费用流问题考虑在寻找最大流的同时最小化总的费用。
7. **最佳边割集/最佳点割集/最小边割集/最小点割集**
- 这些问题涉及在网络中寻找最优的边或点集合，移除它们后可达到特定目的。
8. **最小路径覆盖O(N^3)**
- 最小路径覆盖问题是指在一个有向图中寻找最少数量的路径，使所有顶点都被覆盖。
9. **最小点集覆盖**
- 最小点集覆盖是指在图中寻找最小数量的点，使得所有边至少被一个点覆盖。
#### 数据结构（Data Structures）
1. **左偏树合并复杂度O(logN)**
- 左偏树是一种自平衡的二叉查找树，常用于实现优先队列。
2. **树状数组**
- 树状数组（Binary Indexed Tree）是一种支持高效前缀和查询及更新操作的数据结构。
3. **TRIE树**
- TRIE树是一种用于存储字符串的树形数据结构，非常适合于前缀搜索等应用。
4. **后缀数组**
- 后缀数组是一种用于存储字符串所有后缀排序结果的数据结构，在字符串搜索中有广泛应用。
5. **RMQ离线算法**
- RMQ（Range Minimum Query）问题是指在一维数组中找到指定区间内的最小值，该算法提供了高效的查询方式。
6. **LCA离线算法**
- LCA（Lowest Common Ancestor）问题是指在树形结构中找到两个顶点的最近公共祖先，该算法提供了高效的解决方案。
7. **带权值的并查集**
- 并查集是一种用于处理不交集的合并及查询问题的数据结构，带权值的并查集增加了权值属性。
8. **快速排序**
- 快速排序是一种非常高效的排序算法，平均时间复杂度为O(nlogn)。
9. **最长公共递增子序列O(N^2)**
- 最长公共递增子序列是指在两个序列中寻找最长的递增子序列。
10. **最长公共子序列**
- 最长公共子序列是指在两个序列中寻找最长的相同子序列。
11. **STL中的PRIORITY_QUEUE**
- PRIORITY_QUEUE是C++标准库中的优先队列容器适配器，可以实现高效的堆排序。
12. **堆栈**
- 堆栈是一种先进后出（FILO）的数据结构，常用于实现函数调用栈等场景。
13. **区间最大频率**
- 区间最大频率是指在给定的区间内出现次数最多的元素。
14. **取第K个元素**
- 取第K个元素问题是指在一个序列中找出第K大的元素。
15. **归并排序求逆序数**
- 归并排序是一种稳定的排序算法，可以用来求解逆序数问题。
16. **逆序数推排列数**
- 逆序数是排序理论中的一个重要概念，可用于推导排列的总数。
17. **二分查找**
- 二分查找是一种在有序数组中查找特定元素的有效方法。
18. **所有数位相加**
- 所有数位相加是指将一个整数的所有数字相加得到一个新的数。
#### 数论（Number Theory）
1. **递推求欧拉函数PHI(I)**
- 欧拉函数φ(n)表示小于n且与n互质的正整数的个数。
2. **GCD最大公约数**
- GCD（Greatest Common Divisor）是指两个或多个整数共有的最大的正因数。
3. **模线性方程**
- 模线性方程是指形式为ax≡b(mod m)的方程，求解x。
4. **筛素数**
- 素数筛法是一种高效的生成一定范围内所有素数的方法。
5. **随机素数测试**
- 随机素数测试是一种快速检验大数是否为素数的方法。
6. **组合数学相关**
- 组合数学研究的是从一组对象中选取对象的方式。
7. **POLYA计数**
- POLYA计数是一种用于计算在对称变换下不等价结构的数目。
8. **组合数C(N,R)**
- 组合数是指从n个不同元素中取出r个元素的不同组合的数目。
9. **最大1矩阵**
- 最大1矩阵问题是指在由0和1组成的矩阵中寻找最大正方形区域，其中所有元素均为1。
10. **约瑟夫环问题**
- 约瑟夫环问题是指一个经典的数学问题，涉及到循环报数的游戏。
11. **取石子游戏**
- 取石子游戏是一种典型的博弈问题，涉及策略和数学推理。
12. **集合划分问题**
- 集合划分问题是指将一个集合分成若干个子集，使得每个元素恰好属于一个子集。
13. **大数平方根**
- 大数平方根问题是指对于非常大的数求其平方根。
14. **大数取模的二进制方法**
- 大数取模的二进制方法是指在大数计算中，使用二进制表示和快速幂算法来求模。
15. **线性方程组**
- 线性方程组是一组线性方程的集合，通过代数方法可以求解未知数。
16. **追赶法解周期性方程**
- 追赶法是一种特殊的方法，用于解决一类特殊的周期性方程。
17. **阶乘最后非零位**
- 阶乘最后非零位是指在n!中最后一个非零数字。
#### 模式串匹配问题总结
1. **字符串HASH**
- 字符串HASH是一种将字符串映射为数值的方法，可以快速比较字符串。
2. **KMP匹配算法**
- KMP算法是一种高效的字符串匹配算法，可以在线性时间内完成匹配。
3. **KARP-RABIN字符串匹配**
- KARP-RABIN算法是一种基于哈希的字符串匹配算法，适用于文本搜索等应用场景。
4. **函数名:STRSTR**
- STRSTR函数用于在一个字符串中查找另一个字符串首次出现的位置。
5. **BM算法的改进的算法SUNDAYALGORITHM**
- SUNDAY ALGORITHM是Boyer-Moore算法的一个变种，用于改善匹配效率。
6. **最短公共祖先**
- 最短公共祖先是指两个或多个字符串中的最长共同子序列。
#### 计算几何（Geometry）
1. **GRAHAM**
- GRAHAM算法是一种用于寻找凸包的算法，它基于极角排序的思想。
以上仅为文档内容的摘要，具体实现细节和技术要点需进一步查阅原文档。这些算法模板对于参加ACM/ICPC等编程竞赛的学生来说极为宝贵，有助于提高解决问题的能力和技巧。
