ACM竞赛算法总结：图论、网络流与数据结构

"该资源是一份关于ACM算法竞赛的模板集合，主要涵盖了图论、网络流和数据结构等多个领域的经典算法，适用于解决各种算法竞赛中的问题。" 在这份ACM算法模板中，包含了以下几个核心知识点： 1. **Graph图论**： - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，通过深度优先搜索（DFS）进行标记，用于找出特定性质的路径或节点。 - **无向图找桥**：寻找无向图中的桥，即删除后会导致图不连通的边。 - **无向图连通度(割)**：计算无向图的连通分量，了解其连通性。 - **最大团问题**：寻找图中最大的完全子图，可以采用动态规划和DFS结合的方法求解。 - **欧拉路径**：寻找图中所有边恰好被走过一次的路径，通常用DFS实现。 - **DIJKSTRA算法**：用于寻找加权图中单源最短路径，有数组实现和优化版本。 - **BELLMAN-FORD算法**：处理含有负权边的单源最短路径问题。 - **SPFA算法**：一种改进的Bellman-Ford算法，用于求解单源最短路径。 - **第K短路**：找到起点到其他点的第K条最短路径，可以用Dijkstra或A*算法扩展实现。 2. **Network网络流**： - **二分图匹配**：匈牙利算法，包括DFS和BFS实现，以及Hopcroft-Carp算法，用于寻找最大匹配。 - **最小割**：无向图的最小割问题，可以用来求解最大流问题。 - **最大流**：Dinic算法和HLPP算法，用于在加权有向图中找到最大流量。 - **最小费用流**：寻找满足一定条件下的最小费用最大流。 - **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集**：这些是图的割问题，对网络流分析和优化有重要意义。 3. **Structure数据结构**： - **求某天是星期几**：涉及到日期计算，可能需要理解日期和星期之间的关系。 - **左偏树**：一种特殊的二叉查找树，合并操作的时间复杂度为O(logN)。 - **树状数组**：快速查询和更新区间数据的结构。 - **二维树状数组**：扩展树状数组以处理二维区间操作。 - **TRIE树**：前缀树，用于高效地存储和检索字符串集合。 - **后缀数组**：用于处理字符串问题，如最长公共前后缀、模式匹配等。 - **RMQ（Range Minimum Query）**：区间最小值查询，离线算法可以达到O(N*LOGN)的预处理时间和O(1)的查询时间。 这份模板是ACM/ICPC竞赛选手的重要参考资料，它涵盖了图论、网络流和数据结构的基本算法，帮助参赛者快速理解和解决竞赛中的复杂问题。