吉林大学ACM竞赛编程模板集合

"吉林大学ACM模板.pdf" 是一份由吉林大学ACM竞赛队伍编写的指导文档，包含了ACM/ICPC编程竞赛中常见的算法和数据结构模板。这份资源主要涵盖了图论、网络流和数据结构三个核心领域，旨在帮助参赛者快速解决各种竞赛问题。 在**图论**部分，文档详细介绍了各种算法： 1. **DAG的深度优先搜索标记**：用于处理有向无环图（DAG）的遍历和标记。 2. **无向图找桥**：识别图中的桥（关键边），这些边移除后会增加图的连通分量。 3. **无向图连通度**：计算图的连通分量数量。 4. **最大团问题**：寻找图中最大的完全子图，可以使用动态规划和DFS结合的方法求解。 5. **欧拉路径**：寻找通过所有边一次且仅一次的路径，O(E)表示算法的时间复杂度。 6. **DIJKSTRA**算法两种实现：数组实现和优化后的版本，用于寻找单源最短路径。 7. **BELLMAN-FORD**算法：处理含有负权边的单源最短路径问题。 8. **SPFA（Shortest Path Faster Algorithm）**：一种基于队列的最短路径算法。 9. **第K短路**：寻找除最短路径外的第K短路径，分别使用DIJKSTRA和A*算法实现。 10. **PRIM**算法：最小生成树算法，用于寻找加权无向图的最小连接树。 11. **次小生成树**：找到加权无向图的第二小生成树，时间复杂度为O(V^2)。 12. **最小生成森林问题**：处理多棵树的最小生成树，O(MlogM)的时间复杂度。 13. **有向图最小树形图** 和 **MINIMAL STEINERTREE**：处理有向图的最小树形图问题。 14. **TARJAN**算法：用于计算强连通分量。 15. **弦图判断及PERFECT ELIMINATION点排列**：识别弦图并找到其完美消除顺序。 16. **稳定婚姻问题**：使用Gale-Shapley算法解决，时间复杂度为O(N^2)。 17. **拓扑排序**：对有向无环图进行排序，可以使用DFS或BFS实现。 18. **无向图连通分支** 和 **有向图强连通分支**：查找图的连通分支。 19. **有向图最小点基**：确定有向图的最小点基，O(N^2)的时间复杂度。 20. **FLOYD**算法：计算所有顶点对之间的最短路径。 在**网络流**领域，文档涵盖了： 1. **二分图匹配**：使用DFS、BFS和HOPCROFT-CARP算法实现，目的是找到二分图的最大匹配。 2. **无向图最小割**：寻找割的最小权重。 3. **有上下界**的最小（最大）流问题，以及**DINIC**和**HLPP**最大流算法，它们分别具有O(V^2*E)和O(V^3)的时间复杂度。 4. **最小费用流**：考虑流的费用，提供两种不同时间复杂度的算法，O(V*E*F)和O(V^2*F)。 5. **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集（点连通度）**：涉及网络流中的最优割问题。 6. **最小路径覆盖** 和 **最小点集覆盖**：寻找覆盖图中所有边或顶点的最小集合。 在**数据结构**部分，文档提到了： 1. **求某天是星期几** 的算法。 2. **左偏树**：一种自平衡二叉堆，合并复杂度为O(LOGN)。 3. **树状数组**：高效地支持区间修改和查询操作。 4. **二维树状数组**：扩展树状数组以处理二维区间问题。 5. **TRIE树**：用于高效存储和检索字符串，包括K叉和左儿子右兄弟两种变体。 6. **后缀数组**：用于处理字符串的模式匹配问题，提供了O(N*LOGN)和O(N)两种构建方法。 7. **RMQ（Range Minimum Query）**：区间最小值查询，离线算法的时间复杂度为O(N*LOGN)+O(1)。 这份模板全面覆盖了ACM/ICPC竞赛中可能遇到的主要算法和数据结构，对于准备参赛的学生或者算法爱好者来说，是一份非常有价值的参考资料。