ACM算法模板：图论与网络流详解

"ACM算法模板提供了方便使用的代码库，主要针对ACM/ICPC竞赛，包括图论、网络流和数据结构等多个方面的经典算法。这个模板由吉林大学计算机科学与技术学院2005级的学生jojer&Fandywang整理，适合参赛者参考和学习。" 1. **图论算法** - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，使用DFS进行标记，通常用于拓扑排序或找出关键路径。 - **无向图找桥**：寻找图中的桥，即那些移除后会导致两个原本联通的子图变为不联通的边。 - **无向图连通度(割)**：计算图的连通分量，了解图的联通性。 - **最大团问题**：寻找图中最大的完全子图，可以使用动态规划和DFS结合的方法。 - **欧拉路径**：找到一条从某点出发并经过图中每条边恰好一次的路径。 - **DIJKSTRA算法**：求解单源最短路径，有数组实现和优化的版本，如使用优先队列降低时间复杂度到O(E log E)。 - **BELLMAN-FORD算法**：处理负权边的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：短路径更快算法，也是求解单源最短路径的一种方法，但可能不是最优化的。 - **第K短路**：除了最短路径外，还需要找到第K短的路径，可以基于Dijkstra或A*算法扩展。 - **PRIM算法**：求最小生成树，时间复杂度为O(V^2)。 - **次小生成树**：寻找第二小的生成树，通常使用Kruskal算法，但这里的时间复杂度为O(V^2)。 - **最小生成森林问题**：处理多棵树构成的最小生成森林，可以使用Prim或Kruskal，这里采用并查集优化达到O(M log M)。 - **有向图最小树形图** 和 **MINIMAL STEINERTREE**：这两个是树形图的最小生成树问题，可能涉及到特殊的算法处理。 - **TARJAN强连通分量**：检测图中的强连通分量，即相互可达的节点集合。 - **弦图判断** 及 **弦图的PERFECT ELIMINATION点排列**：弦图是指在一个圆上的点之间连接的边形成的图，这些算法用于识别和处理弦图。 - **稳定婚姻问题**：通过Gale-Shapley算法解决稳定匹配问题，时间复杂度为O(N^2)。 2. **网络流算法** - **二分图匹配**：通过匈牙利算法（DFS和BFS实现）以及HOPCROFT－CARP算法，解决二分图中最大匹配问题。 - **KUHNMUNKRAS算法**：求解二分图的最佳匹配，具有较高的效率。 - **无向图最小割**：找到最小割，将图分成两部分，使得割边的总权重最小。 - **有上下界的最小(最大)流**：在网络流中考虑流量限制的上下界，寻求最优解。 - **DINIC算法**：求解最大流问题，时间复杂度为O(V^2*E)。 - **HLPP算法**：高效的最大流算法，时间复杂度为O(V^3)。 - **最小费用流**：同时考虑流量和费用，找到总费用最小的可行流方案。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集（点连通度）**：不同角度探讨图的割问题。 - **最小路径覆盖**：寻找覆盖所有节点的最小数量的路径。 - **最小点集覆盖**：找到最小的点集合，使得每个边至少被一个点覆盖。 3. **数据结构算法** - **求某天是星期几**：通过日期计算对应的星期。 - **左偏树**：一种特殊的二叉堆，用于快速合并操作，合并复杂度为O(LOGN)。 - **树状数组**：用于高效地处理区间查询和修改问题。 - **二维树状数组**：对二维数组进行类似操作，扩展树状数组的功能。 - **TRIE树**：用于字符串检索的树形结构，分为K叉和左儿子右兄弟两种实现方式。 - **后缀数组**：存储字符串的所有后缀，可以快速查找模式串在文本中的位置，有O(N*LOGN)和O(N)的构造方法。 - **RMQ（Range Minimum Query）**：区间查询最小值，离线算法可以在O(N*LOGN)+O(1)时间内完成预处理和查询。 这些算法是ACM/ICPC竞赛中常见的问题解决方案，通过掌握和熟练运用这些模板，参赛者能够更高效地解决各类竞赛题目。