吉林大学ACM/ICPC代码库：经典算法模板集

"ACM模板.pdf" 是一个包含ACM/ICPC竞赛代码库的文档，主要涵盖了图论、网络流、数据结构、排列组合、模式匹配和计算几何等多个领域的经典算法模板。这份资料由吉林大学计算机科学与技术学院2005级2007-2008年的ACMGroup1成员编写和修订，其中包括了jojer, sharang, xwbsw, Liuctic, 以及Fandywang等人的贡献。 在图论部分，文档详细列举了各种算法： 1. DAG的深度优先搜索标记：用于遍历有向无环图（DAG）并进行标记。 2. 无向图找桥：查找无向图中的桥，即删除后会导致连通性改变的边。 3. 无向图连通度（割）：计算无向图的连通分量数量。 4. 最大团问题DP+DFS：动态规划和深度优先搜索结合解决最大团问题，寻找图中最大的完全子图。 5. 欧拉路径：找到起点到终点经过每条边恰好一次的路径。 6. Dijkstra算法：两种实现，数组实现和优化版本（O(E log E)），用于求单源最短路径。 7. Bellman-Ford算法：O(VE)时间复杂度求解单源最短路径，可处理负权边。 8. SPFA算法：一种快速最短路径算法。 9. 第K短路：利用Dijkstra或A*算法求解除最短路径外的其他短路径。 10. Prim算法：O(V^2)时间复杂度求最小生成树。 11. 次小生成树：另一种求最小生成树的方法，时间复杂度为O(M log M)。 12. 有向图最小树形图：构建有向图的最小树形图。 13. Tarjan算法：求解强连通分量。 14. 弦图判断及完美消除点排列：识别弦图并找到其完美消除顺序。 15. 稳定婚姻问题：通过Gale-Shapley算法解决稳定性匹配问题。 16. 拓扑排序：对有向无环图进行排序。 17. 无向图连通分支：使用DFS或BFS找到无向图的连通分支。 18. 有向图强连通分支：同样使用DFS或BFS找到有向图的强连通分支。 19. 有向图最小点基：找到有向图的最小点基，时间复杂度为O(N^2)。 20. Floyd算法：求解所有顶点对之间的最短路径，同时找出最小环。 21. 2-SAT问题：解决满足2-CNF约束的布尔变量赋值问题。 在网络流部分，文档涵盖了： 1. 二分图匹配：三种不同的匈牙利算法实现，包括DFS、BFS以及HOPCROFT-CARP算法。 2. Kuhn-Munkres算法：解决二分图的最佳匹配问题，时间复杂度为O(M*M*N)。 3. 无向图最小割：求解无向图的最小割，用于切断连接。 4. 有上下界最小（最大）流：处理带权重和流量限制的网络流问题。 5. Dinic算法：最大流算法，时间复杂度为O(V^2*E)。 6. HLPP算法：另一种最大流算法，时间复杂度为O(V^3)。 7. 最小费用流：考虑费用的网络流问题，两种不同时间复杂度的实现。 8. 最佳边割集、最佳点割集、最小边割集和最小点割集（点连通度）：这些算法用于网络优化问题，如最小费用流的边和点割集。 9. 最小路径覆盖：找到最小数量的路径覆盖所有顶点。 10. 最小点集覆盖：寻找最小的点集，使得每个边至少有一个端点在集合中。 在数据结构部分，虽然没有列出详细算法，但可能涉及常见数据结构的实现和操作，如堆、树、队列、栈、链表、哈希表等。 这个代码库对于准备ACM/ICPC竞赛的程序员来说是宝贵的资源，它提供了各种算法的实现，可以帮助参赛者快速理解和应用这些算法解决实际问题。