ACM竞赛常用算法与代码集合

"该资源是一个ACM/ICPC竞赛常用的算法代码库，主要涵盖了图论、网络流和数据结构等多个领域的经典算法实现，适合于编程竞赛训练和算法学习。" 在ACM/ICPC竞赛中，掌握高效算法是至关重要的。这个代码库包含了多种常用的算法，以下是它们的详细介绍： 1. **Graph图论** - **DAG的深度优先搜索标记**：用于遍历有向无环图（DAG），标记节点并处理相关任务。 - **无向图找桥**：找出图中的桥（断点），桥是使得去掉后会导致图分块的边。 - **无向图连通度**：计算图的连通分量，了解图的分块情况。 - **最大团问题**：寻找一个图中最大的完全子图，可以使用动态规划+DFS解决。 - **欧拉路径**：找到一个图中起点和终点相同时，所有边恰好使用一次的路径。 - **DIJKSTRA算法**：数组实现，用于求解单源最短路径问题，时间复杂度为O(N^2)。 - **DIJKSTRA优化**：使用优先队列（如二叉堆），时间复杂度降低到O(E*LOGE)。 - **BELLMAN-FORD算法**：处理负权边的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：短路最快算法，适用于负权边的情况。 - **第K短路**：除了最短路径外，还可以找到第K条最短路径，可采用DIJKSTRA或A*算法进行扩展。 - **PRIM算法**：求最小生成树，时间复杂度为O(V^2)。 - **次小生成树**：寻找第二小的生成树，通常使用贪心策略。 - **最小生成森林问题**：处理多棵树的最小生成树，可以使用Prim或Kruskal算法，优化后的时间复杂度为O(MLOGM)。 - **有向图最小树形图**：找到图的最小树形图，用于解决树形图的构造问题。 - **TARJAN强连通分量**：检测和找出图中的强连通分量。 - **弦图判断**：判断一个图是否是弦图，弦图是具有特定性质的图。 - **弦图的PERFECT ELIMINATION点排列**：处理弦图的一种方法。 - **稳定婚姻问题**：用Gale-Shapley算法解决稳定婚姻配对问题，时间复杂度为O(N^2)。 - **拓扑排序**：对有向无环图进行排序，确保没有前驱关系的节点先被处理。 - **无向图连通分支**：通过DFS或BFS找到图的连通分支。 - **有向图强连通分支**：利用DFS找到有向图的强连通分支。 - **有向图最小点基**：找到有向图的最小点基，用于图的简化或压缩。 2. **Network网络流** - **二分图匹配**：使用DFS或BFS实现的匈牙利算法，解决匹配问题。 - **HOPCROFT-CARP算法**：另一种二分图匹配算法，优化了匈牙利算法。 - **KUHN-MUNKRAS算法**：最优匹配算法，适用于大规模问题，时间复杂度为O(M*M*N)。 - **无向图最小割**：寻找最小割以分割图，常用于网络优化问题。 - **有上下界最小（最大）流**：处理流量有上限和下限的网络流问题。 - **DINIC算法**：最大流算法，时间复杂度为O(V^2*E)。 - **HLPP最大流**：高勒-洛普豪斯-普罗科波夫算法，时间复杂度为O(V^3)。 - **最小费用流**：考虑了每条边的费用，最小化总费用的同时满足最大流量。 - **最小费用流优化**：时间复杂度为O(V^2*F)，进一步优化最小费用流问题。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集**（点连通度）：分别处理不同场景下的割集问题。 - **最小路径覆盖**：找到覆盖所有顶点的最小路径集合。 - **最小点集覆盖**：找到覆盖所有边的最小顶点集合。 3. **Structure数据结构** - **求某天是星期几**：基于蔡勒公式，计算给定日期对应星期的算法。 - **左偏树合并复杂度O(LOGN)**：左偏树是一种自平衡二叉树，合并操作的时间复杂度较低。 - **树状数组**：一种高效的数据结构，用于快速更新和查询区间加法和求和问题。 这些算法是ACM/ICPC竞赛中的基础，学习并熟练掌握它们对于提升算法能力和解决实际问题大有裨益。通过这个代码库，你可以看到各种算法的实现细节，有助于理解和实践这些算法。