ACM算法代码集：图论、网络流与数据结构

"ACM代码库.pdf" 这篇文档是一个关于ACM竞赛编程的代码资源集合，涵盖了图论、网络流和数据结构等多个重要领域。以下是其中的关键知识点： 1. **图论** - **深度优先搜索（DFS）**：在有向无环图（DAG）中用于标记和寻找特定路径。 - **找桥**：在无向图中识别那些移除后会断开连通性的边。 - **连通度**：计算无向图的连通分量或割点。 - **最大团问题**：寻找图中最大的完全子图，通常使用动态规划和DFS。 - **欧拉路径**：找到一个从任意点出发并遍历所有边恰好一次的路径，时间复杂度为O(E)，其中E是边的数量。 - **Dijkstra算法**：用于求解单源最短路径，有数组实现的O(N^2)版本和优先队列优化后的O(E log E)版本。 - **Bellman-Ford算法**：解决单源最短路径问题，可处理负权边，时间复杂度为O(VE)。 - **SPFA算法**：Shortest Path Faster Algorithm，一种快速但不保证最优化的Dijkstra变种。 - **第K短路**：使用Dijkstra或A*算法扩展来寻找除最短路径外的第K短路径。 - **Prim算法**：构造最小生成树（MST），适用于加权无向图。 - **Kruskal算法**：另一种MST构造方法，适用于加权无向图，常用于求最小生成森林。 - **最小树形图**：有向图中的最小树形图问题。 - **Steiner树**：在图中找到连接特定顶点子集的最小树形结构。 - **TARJAN强连通分量**：检测有向图中的强连通分量。 - **弦图**：涉及弦图的性质和识别算法，包括完美消除序列。 - **拓扑排序**：对有向无环图进行排序，使得对于每条有向边，其起点都排在终点之前。 2. **网络流** - **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp算法。 - **Kuhn-Munkres算法**：求解二分图的最大匹配，时间复杂度为O(M*M*N)，M为边的数量，N为顶点的数量。 - **最小割**：在无向图中寻找能分割成两个独立子集的最小边集合。 - **最小费用流**：在满足容量约束的同时最小化总费用，有O(V*E*F)和O(V^2*F)两种算法。 - **最大流**：Dinic算法以O(V^2*E)的时间复杂度求解，HLPP算法以O(V^3)的时间复杂度求解。 3. **数据结构** - **求星期几**：根据日期计算出该日期是星期几的算法。 - **左偏树**：一种自平衡二叉堆，合并操作的时间复杂度为O(log N)。 - **树状数组**：用于高效地执行区间更新和查询操作的数据结构。 - **二维树状数组**：扩展树状数组以处理二维区间的问题。 - **Trie树**：前缀树，用于存储字符串并快速查找和插入。 - **后缀数组**：构建和应用后缀数组进行字符串处理，有O(N*LOG N)和O(N)两种构建方法。 - **RMQ（范围最小/最大查询）**：离线算法和ST（Sqrt-Decomposition）算法分别用于求解区间内最小值和最大值，提供不同的时间复杂度优化。 - **LCA（最近公共祖先）**：求解树中两个节点的最近公共祖先，可以使用RMQ离线算法优化。 这些知识点是ACM竞赛中常见的问题类型，学习和掌握它们将有助于解决各种复杂算法挑战。