吉林大学ACM竞赛代码模板集合

"吉林大学ACM例程模板" 这篇资源主要涵盖了ACM竞赛中的常见算法和数据结构，适合参赛者参考和学习。这份模板由吉林大学ACMGroup1的成员编写和更新，提供了丰富的代码实例和理论解释。 1. **Graph图论** - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，深度优先搜索（DFS）用于标记节点，例如计算后序遍历。 - **无向图找桥**：寻找无向图中的桥，即删除后导致连通性改变的边。 - **无向图连通度(割)**：计算无向图的连通分量，了解图的割点和关键边。 - **最大团问题**：使用动态规划和DFS解决寻找图中最大完全子图的问题。 - **欧拉路径**：寻找一个图中起点和终点的欧拉路径，如果图是连通且所有边的度数都是偶数。 - **DIJKSTRA算法**：通过两种不同的实现（数组和优先队列）找到单源最短路径。 - **BELLMAN-FORD算法**：解决带有负权边的单源最短路径问题。 - **SPFA算法**：一种基于队列的最短路径算法，比Dijkstra更适应负权重边的情况。 - **第K短路**：扩展Dijkstra或A*算法来找到除了最短路径之外的第K条最短路径。 - **PRIM算法**：用于找到无向图的最小生成树，时间复杂度为O(V^2)。 - **次小生成树**：寻找图的次小生成树，通常使用Kruskal算法的变种。 - **最小生成森林问题**：处理多棵树的最小生成树，可以使用Prim或Kruskal在O(M log M)的时间内解决。 - **有向图最小树形图**：寻找有向图的最小树形图，与最小生成树类似。 - **TARJAN强连通分量**：用于识别有向图中的强连通分量。 - **弦图判断及PERFECT ELIMINATION点排列**：在图论中，弦图和完美消除顺序与图的矩阵表示有关。 - **稳定婚姻问题**：应用Gale-Shapley算法来解决稳定匹配问题。 2. **Network网络流** - **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp算法和Kuhn-Munkres算法，用于找到最大匹配。 - **无向图最小割**：寻找无向图中的最小割，可以用于计算两个顶点集合间的最大流量。 - **有上下界的最小(最大)流**：处理流量有上下界限制的网络流问题。 - **Dinic算法**：实现最大流，时间复杂度为O(V^2*E)。 - **HLPP最大流**：采用 Hopcroft-Karp 算法求解最大流，时间复杂度为O(V^3)。 - **最小费用流**：在考虑边的费用时寻找最大流，有两种不同复杂度的实现。 - **最佳边割集和最佳点割集**：寻找具有最小费用的边割集或点割集，优化网络流问题。 - **最小边割集和最小点割集（点连通度）**：寻找最小割以衡量图的点连通性。 - **最小路径覆盖**：找到覆盖所有边的最小路径集合。 - **最小点集覆盖**：寻找覆盖所有边的最小顶点集合。 3. **Structure数据结构** - **求某天是星期几**：算法可能涉及计算日期和星期之间的关系。 - **左**：这部分内容被省略，可能是关于某种数据结构操作或算法的说明。 这份模板全面地涵盖了ACM竞赛中常见的算法和数据结构，对准备参赛的学生来说是一份宝贵的参考资料。