吉林大学ACM/ICPC代码库：图论与网络流算法总结

"ACM模板（吉林大学）包含吉林大学计算机科学与技术学院2005级2007-2008年的ACM/ICPC竞赛代码库，涵盖图论、网络流和数据结构等多个算法领域。" 这篇摘要详细列出了ACM竞赛中常用的算法模板，主要包括以下几个部分： 1. **Graph图论**： - **DAG的深度优先搜索标记**：在有向无环图(DAG)中进行深度优先搜索，用于标记顶点的某种属性。 - **无向图找桥**：查找无向图中的桥，即那些移除后会增加连通分量的边。 - **无向图连通度(割)**：计算图的连通性，包括寻找割点和割边。 - **最大团问题**：通过动态规划和DFS解决图的最大团问题，寻找最大的完全子图。 - **欧拉路径**：找到一个从起点到终点经过每条边恰好一次的路径。 - **DIJKSTRA算法**：两种实现方式，数组实现和优化后的版本，用于寻找图中单源最短路径。 - **BELLMAN-FORD算法**：求解单源最短路径，能处理负权边。 - **SPFA算法**：SHORTEST PATH FASTER ALGORITHM，快速求解单源最短路径。 - **第K短路**：分别使用DIJKSTRA和A*算法求解。 - **PRIM算法**：最小生成树算法，用于找到无向图中最小的生成树。 - **次小生成树**：另一种O(V^2)的时间复杂度算法。 - **最小生成森林问题**：Kruskal或Prim的O(M log M)版本，处理多棵树的最小生成树问题。 - **有向图最小树形图**：MINIMAL STEINERTREE算法，与最小生成树类似。 - **TARJAN算法**：求解图的强连通分量。 - **弦图判断**：识别弦图及其完美消除序列。 - **稳定婚姻问题**：Gale-Shapley算法，寻找稳定的一对一配对。 - **拓扑排序**：对有向无环图进行排序。 2. **Network网络流**： - **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及HOPCROFT-CARP算法。 - **KUHN-MUNKRAS算法**：用于解决二分图的最佳匹配问题。 - **最小割**：在无向图中找到最小的割，分为无上下界和有上下界的情况。 - **DINIC算法**：最大流算法，具有O(V^2*E)的时间复杂度。 - **HLPP算法**：另一种最大流算法，时间复杂度为O(V^3)。 - **最小费用流**：考虑边的权重，寻找最大流同时最小化总费用。 - **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集**：涉及图的割集优化问题。 - **最小路径覆盖**：寻找覆盖所有节点的最小路径集合。 - **最小点集覆盖**：寻找覆盖所有边的最小顶点集合。 3. **Structure数据结构**： - **求某天是星期几**：基于日期的计算问题。 - **左偏树**：一种特殊的二叉堆，用于高效合并操作。 - **树状数组**：快速更新和查询区间加法的问题。 - **二维树状数组**：扩展树状数组以处理二维区间查询和更新。 - **TRIE树**：用于字符串搜索和存储的前缀树结构，包括K叉和左儿子右兄弟两种实现。 - **后缀数组**：处理字符串后缀的排序，有O(N*LOGN)和O(N)两种构造方法。 - **RMQ(Range Minimum Query)**：求解区间最小值问题，离线算法为O(N*LOGN)+O(1)。 这些算法和数据结构是ACM/ICPC竞赛中常见的题目类型，对于参赛者来说理解和掌握这些内容是提高解题能力的关键。