ACM竞赛代码库：图论与网络流算法集合

"ACM模板代码" ACM（国际大学生程序设计竞赛）是全球规模宏大、影响力广泛的大学生程序设计竞赛，旨在提升学生的算法设计、逻辑分析及编程技能。本资源是一个全面且常用的ACM代码库，特别适合准备参加ACM竞赛的同学学习和参考。 这个代码库涵盖了许多重要的算法和数据结构，主要分为以下几个部分： 1. **Graph图论**： - **DAG的深度优先搜索标记**：用于处理有向无环图（DAG）的遍历。 - **无向图找桥**：识别图中的桥（断点），桥连接两个不连通的子图。 - **无向图连通度**：计算图的连通分量。 - **最大团问题**：寻找图中最大的完全子图，可以用动态规划和DFS解决。 - **欧拉路径**：找到一条通过图中所有边恰好一次的路径。 - **DIJKSTRA算法**：求解单源最短路径，有两种实现方式，数组实现的时间复杂度为O(N^2)，优先队列实现的时间复杂度为O(E*LOGE)。 - **BELLMAN-FORD算法**：处理存在负权边的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：一种改进的Bellman-Ford算法，平均效率更高。 - **第K短路**：除了最短路径外，寻找第K短的路径。 - **PRIM算法**：用于求解加权无向图的最小生成树。 - **次小生成树**：找到除最小生成树外的第二小生成树，时间复杂度为O(V^2)。 - **最小生成森林问题**：处理多棵树的最小生成树，可用Prim或Kruskal算法，时间复杂度为O(MLOGM)。 - **有向图最小树形图** 和 **MINIMAL STEINERTREE**：求解树形图的最小生成树。 - **TARJAN强连通分量**：识别图中的强连通分量。 - **弦图判断**：检测一个图是否是弦图，并找到其完美消除顺序。 - **稳定婚姻问题**：应用Gale-Shapley算法，解决稳定匹配问题。 - **拓扑排序**：对有向无环图进行排序。 - **无向图连通分支**：利用DFS或BFS查找图的连通分支。 - **有向图强连通分支**：识别有向图中的强连通分量。 - **有向图最小点基**：找到有向图中最小的点集，使得这些点可以到达所有其他点。 2. **Network网络流**： - **二分图匹配**：通过匈牙利算法（DFS和BFS实现）求解二分图的最大匹配。 - **HOPCROFT-CARP算法**：也是用于二分图的最佳匹配。 - **KUHN-MUNKRAS算法**：求解二分图最佳匹配的高效算法，时间复杂度为O(M*M*N)。 - **无向图最小割**：寻找能将图分割成两部分的最小边集合。 - **有上下界的最小(最大)流**：在网络流中处理有上下界流量的问题。 - **DINIC算法**：实现最大流，时间复杂度为O(V^2*E)。 - **HLPP算法**：高莱-洛夫拉斯最大流算法，时间复杂度为O(V^3)。 - **最小费用流**：在满足流量约束的同时，寻找总费用最小的流。 - **最佳边割集**、**最佳点割集**、**最小边割集** 和 **最小点割集（点连通度）**：涉及图的割集问题。 - **最小路径覆盖**：寻找覆盖图中所有边的最小路径集合。 - **最小点集覆盖**：找到最小的点集，使得每个边至少有一个端点被覆盖。 3. **Structure数据结构**： - **求某天是星期几**：计算日期对应的星期。 - **左偏树**：一种特殊的二叉堆，用于高效地处理合并操作。 - **树状数组**：也称为线段树，用于区间查询和修改操作。 这个ACM代码库为学习者提供了丰富的算法实例和实现，有助于理解和掌握竞赛中常见的问题解决策略，对于提升编程能力和算法思维具有很高的价值。