ACM竞赛常用代码集合

"ACM代码库包含了ACM竞赛中常用的各种算法和代码，适用于学习和参考。这份资源来自吉林大学ACMGroup1，由不同成员修订和完善，旨在帮助参赛者和学习者掌握ACM竞赛所需的编程技巧和算法知识。" 在ACM/ICPC竞赛中，参赛者通常需要熟悉并应用多种算法来解决复杂的问题。这份代码库涵盖了以下几个主要的知识点： 1. **Graph图论**： - **DAG的深度优先搜索标记**：用于遍历无环图，标记节点状态。 - **无向图找桥**：检测无向图中的桥（断点），这些桥是使得图不连通的关键边。 - **无向图连通度**：计算无向图的连通分量，理解图的分割情况。 - **最大团问题**：寻找图中最大的完全子图，可以通过动态规划和深度优先搜索实现。 - **欧拉路径**：找到一条通过图中所有边的路径，如果存在的话。 - **DIJKSTRA**：寻找单源最短路径，两种实现方式：数组实现（时间复杂度O(N^2)）和优化后的版本（时间复杂度O(E log E)）。 - **BELLMAN-FORD**：处理负权边的单源最短路径问题，时间复杂度O(VE)。 - **SPFA**：一种快速求解单源最短路径的算法，适用于有负权重的边。 - **第K短路**：不仅求最短路径，还可以找到第K条最短路径，分别使用DIJKSTRA和A*算法实现。 2. **最小生成树**： - **PRIM**：Prim算法用于构建最小生成树，时间复杂度O(V^2)。 - **次小生成树**：求解次小生成树，有时需要处理多棵最小生成树，例如Kruskal算法的变种，时间复杂度O(M log M)。 - **最小生成森林**：处理图中含有负权边的情况，可能需要多个最小生成树。 - **有向图最小树形图**：在有向图中寻找最小树形图，即最小生成树的一种形式。 3. **强连通分量**： - **TARJAN**算法：用于找出图中的强连通分量，即在有向图中每个节点都可以到达其他所有节点的子图。 4. **其他图论问题**： - **弦图判断**：识别弦图，弦图是指一个有向图中没有环的边。 - **弦图的PERFECT ELIMINATION**：弦图的完美消除顺序。 - **稳定婚姻问题**：Gale-Shapley算法，用于寻找稳定匹配的解，时间复杂度O(N^2)。 - **拓扑排序**：对于有向无环图(DAG)的排序。 - **有向图连通分支**：使用DFS或BFS查找有向图的连通分支。 - **有向图最小点基**：寻找最小的点集，使得每条边指向该集合中的某个点。 5. **网络流**： - **二分图匹配**：匈牙利算法的不同实现，用于寻找二分图的最大匹配。 - **最小割**：无向图最小割问题，求解网络的最大流量。 - **最大流**：包括Dinic算法（时间复杂度O(V^2*E)）和HLPP算法（时间复杂度O(V^3)）。 - **最小费用流**：在满足流量约束的同时最小化总费用，有两种不同的实现。 - **最佳边割集、最佳点割集、最小边割集和最小点割集**：这些是网络流的特殊情况，用于特定的优化问题。 - **最小路径覆盖**：寻找覆盖所有边的最小路径集合。 - **最小点集覆盖**：找到覆盖所有边的最小顶点集合。 6. **数据结构**： - **求某天是星期几**：涉及日期计算，可能用到日历算法。 - **左偏树**：一种自平衡二叉堆，用于高效地处理插入和删除操作。 这个代码库是学习和研究ACM算法的一个宝贵资源，它包含了大量经典算法的实现，有助于提升编程和算法设计能力。对于想要参加ACM竞赛或深入理解算法的程序员来说，这是一个非常有价值的参考资料。