ACM算法全览：图论、网络流与数据结构

"ACM算法-ACM/ICPC代码库" 这篇摘要涵盖了ACM算法竞赛中的关键知识点，包括图论、网络流和数据结构。这些是编程竞赛中常见的问题解决工具，对于提升算法能力非常有帮助。 1. **图论** - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，深度优先搜索（DFS）可以用于标记节点的属性，如拓扑排序。 - **无向图找桥**：在无向图中，桥是指移除后导致连通性降低的边。 - **无向图连通度(割)**：计算图的连通分支数量，通常通过DFS或BFS来确定。 - **最大团问题**：寻找图中最大的完全子图，可以用动态规划（DP）和DFS解决。 - **欧拉路径**：寻找访问图中所有边一次且仅一次的路径，O(E)时间复杂度。 - **DIJKSTRA算法**：求解单源最短路径，有数组实现O(N^2)和优先队列实现O(E*LOGE)两种方式。 - **BELLMAN-FORD算法**：处理负权边的单源最短路径问题，O(VE)时间复杂度。 - **SPFA算法**：最短路径快速算法，用于近似求解最短路径。 - **第K短路**：找到除了最短路径之外的第K短路径，可以使用DIJKSTRA或A*算法扩展。 - **PRIM算法**：最小生成树算法，用于寻找无向图中权重最小的边集合，连接所有节点。 - **次小生成树**：找到第二小的生成树，时间复杂度为O(V^2)。 - **最小生成森林问题**：求解有向图的最小生成树，可以使用Prim或Kruskal算法，O(MLOGM)时间复杂度。 - **有向图最小树形图**：在有向图中构造一棵树形子图，使边权之和最小。 - **MINIMAL STEINER TREE**：最小斯蒂林树问题，寻找连接所有点的最小树形子图。 - **TARJAN强连通分量**：找出图中的强连通组件，即任意两点间都存在双向路径。 - **弦图判断**：识别图是否为弦图，弦图中每条边不是环的一部分。 - **弦图的PERFECT ELIMINATION点排列**：一种优化弦图的操作。 - **稳定婚姻问题**：用O(N^2)时间解决稳定匹配问题。 - **拓扑排序**：对有向无环图进行排序，使得每条边指向的节点都在其前面。 - **无向图连通分支**：使用DFS或BFS找出图的所有连通分支。 - **有向图强连通分支**：确定有向图的强连通组件，DFS-BFS邻接阵实现。 - **有向图最小点基**：寻找有向图中最小的点集，使得每个节点都能通过这组点到达其他节点。 - **FLOYD算法**：求解所有节点对之间的最短路径，O(V^2)时间复杂度。 - **2-SAT问题**：满足2-CNF形式布尔逻辑的解决方案，是图论和逻辑推理问题的一种。 2. **网络流** - **二分图匹配**：寻找二分图中最大匹配量，有DFS、BFS和Hopcroft-Carp算法实现。 - **KUHN-MUNKRAS算法**：求解二分图的最佳匹配，O(M*M*N)时间复杂度。 - **无向图最小割**：寻找能将图分割成两个子集的最小边集合，O(N^3)时间复杂度。 - **有上下界的最小(最大)流**：在网络流问题中考虑边的流量上限和下限。 - **DINIC算法**：求解网络的最大流，O(V^2*E)时间复杂度。 - **HLPP算法**：赫尔普曼-洛普普特最大流算法，O(V^3)时间复杂度。 - **最小费用流**：在保证流量的前提下最小化总费用，有O(V*E*F)和O(V^2*F)两种复杂度算法。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集（点连通度）**：与网络流相关的割问题，涉及最小化某些成本或最大化流量。 - **最小路径覆盖**：寻找覆盖所有节点的最小路径集合，O(N^3)时间复杂度。 - **最小点集覆盖**：寻找最小的点集，使得每个边至少被该集合中的一个点覆盖。 3. **数据结构** - **求某天是星期几**：根据日期计算星期，涉及到日期和时间的处理。 - **左偏树**：一种自平衡的二叉堆，合并复杂度为O(LOG N)。 - **树状数组**：一种用于高效计算区间和的数据结构。 - **二维树状数组**：对树状数组的扩展，处理二维区间查询和更新。 - **TRIE树**：前缀树，用于高效存储和查找字符串。 - **后缀数组**：处理字符串后缀，有O(N * LOG N)和O(N)两种构建方法。 - **RMQ（范围最小/最大查询）**：在线或离线算法，用于快速查询区间内的最小值或最大值。 - **LCA（最近公共祖先）**：找到树中两个节点的最近公共祖先，有离线算法O(E)+O(1)和ST算法O(NLOGN + Q)。 - **带权值的并查集**：并查集的扩展，支持权重操作。 - **快速排序**：快速高效的排序算法，平均时间复杂度为O(NLOGN)。 以上知识涵盖了ACM/ICPC竞赛中常见的算法和数据结构，学习和掌握这些内容对于提高编程竞赛水平至关重要。