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

"这份资源是一份关于ACM算法的详细模板，涵盖了图论、网络流和数据结构等多个方面的经典算法，旨在帮助提升ACM竞赛或算法编程能力。" 在ACM算法模板中，主要涉及以下几个核心知识点： 1. **图论**： - **DAG的深度优先搜索标记**：用于遍历有向无环图（DAG），并进行标记处理。 - **无向图找桥**：识别图中的桥（割边），即移除后会导致图分成分离部分的边。 - **无向图连通度**：计算图的连通分量，理解图的结构。 - **最大团问题**：寻找图中最大的完全子图，可以使用动态规划和DFS结合的方法求解。 - **欧拉路径**：寻找图中起点到终点经过每条边恰好一次的路径，O(E)复杂度。 - **Dijkstra算法**：求解单源最短路径，有数组实现（O(N^2)）和优化版本（O(E*LOGE)）。 - **Bellman-Ford算法**：处理负权边的单源最短路径问题，O(VE)复杂度。 - **SPFA算法**：Shortest Path Faster Algorithm，快速求解单源最短路径，但不保证最优化时间复杂度。 - **第K短路**：通过Dijkstra或A*算法扩展，找到除了最短路径之外的第K短路径。 - **Prim算法**：用于求解最小生成树，O(V^2)复杂度。 - **Kruskal算法**：另一种求最小生成树的方法，O(MLOGM)复杂度。 - **有向图最小树形图**：在有向图中构建一棵最小树形图。 - **Tarjan算法**：求解强连通分量，O(V+E)复杂度。 - **弦图判断**及**完美消除序**：弦图的性质及其在图论中的应用。 - **稳定婚姻问题**：Gale-Shapley算法，O(N^2)复杂度。 - **拓扑排序**：对有向无环图进行排序，可以使用DFS或BFS实现。 - **无向图连通分支**：通过DFS或BFS找到图的连通分支。 - **有向图强连通分支**：同样使用DFS或BFS，但针对有向图。 - **有向图最小点基**：寻找图中最小的点集，使得每个点都可以到达其他所有点。 2. **网络流**： - **二分图匹配**：通过匈牙利算法实现，包括DFS和BFS两种方式。 - **Kuhn-Munkres算法**：求解二分图的最佳匹配，O(M*M*N)复杂度。 - **最小割**：在无向图中寻找最小割，可以用于解决一些优化问题。 - **最大流**：Dinic算法（O(V^2*E)）和HLPP算法（O(V^3)）等，用于在网络中寻找最大流量。 - **最小费用流**：考虑边的权重，求解最小总费用下的最大流问题。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集**：涉及图的割集理论，用于优化网络中的路径或连接。 - **最小路径覆盖**：寻找覆盖所有边的最小路径集合。 - **最小点集覆盖**：找到覆盖所有边的最小点集合。 3. **数据结构**： - **求某天是星期几**：涉及日期计算，可能用到日历算法。 - **左偏树**：一种特殊的二叉堆，常用于实现高效合并操作。 - **树状数组**：也称为线段树，用于区间查询和更新操作。 - **二维树状数组**：扩展树状数组以处理二维区间问题。 - **Trie树**：用于字符串检索和前缀匹配，有K叉Trie和左儿子右兄弟两种实现。 - **后缀数组**：存储字符串的所有后缀，用于字符串处理和模式匹配，有线性和线性对数时间复杂度的构造方法。 - **RMQ（Range Minimum Query）**：求解区间最小值问题，有离线算法和在线算法实现。 这份模板为学习ACM算法提供了丰富的参考资料，覆盖了竞赛编程中常见的问题和解决方案，是提高算法能力的宝贵资源。