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

"ACM算法模板" ACM（国际大学生程序设计竞赛）算法模板涵盖了图论、网络流和数据结构等多个重要领域，是参赛者必备的技能和知识库。以下是对这些领域的详细解释： 1. **Graph图论** - **DAG的深度优先搜索标记**：在有向无环图(DAG)中，深度优先搜索用于标记节点，例如判断有向无环图的拓扑排序。 - **无向图找桥**：寻找无向图中的桥，即那些移除后会增加连通组件数量的边。 - **无向图连通度(割)**：计算图的连通性，即最少删除多少边才能使图变得不连通。 - **最大团问题**：寻找图中最大的完全子图，可以用动态规划和DFS解决。 - **欧拉路径**：在具有特定条件的图中找到一条经过所有边恰好一次的路径。 - **DIJKSTRA**：用于寻找单源最短路径，数组实现的时间复杂度为O(N^2)，而使用优先队列可以优化到O(E*LOGE)。 - **BELLMAN-FORD**：解决负权边情况下的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA**：短路径更快算法，也是求解单源最短路径的一种方法。 - **第K短路**：除了最短路径外，还需要寻找第K短的路径，可以使用DIJKSTRA或A*算法进行扩展。 - **PRIM求MST**：最小生成树算法之一，用于找到连接所有顶点的最短边集合，时间复杂度为O(ELOGE)。 - **次小生成树**：不是最小生成树，但边的权重次于最小生成树中的边，通常使用Kruskal算法。 - **最小生成森林问题**：处理有环图，使用Prim或Kruskal算法，时间复杂度为O(MLOGM)。 - **有向图最小树形图**：找到有向图的最小树形图，也称为有向生成树。 - **TARJAN强连通分量**：检测有向图中的强连通分量，即每个节点都能到达其他所有节点的子图。 - **弦图判断**：判断图是否是弦图，并找出完美消除序列。 - **稳定婚姻问题**：用Gale-Shapley算法解决，时间复杂度为O(N^2)。 - **拓扑排序**：对DAG进行排序，使得对于每条有向边 (u, v)，节点u总是在v之前。 2. **Network网络流** - **二分图匹配**：匈牙利算法通过DFS或BFS实现，找到二分图中最大匹配。 - **KUHNMUNKRAS算法**：用于求解二分图的最佳匹配，时间复杂度为O(M*M*N)。 - **无向图最小割**：寻找最小割以分割图，时间复杂度为O(N^3)。 - **有上下界的最小(最大)流**：在网络流问题中考虑边的容量限制。 - **DINIC最大流**：改进的网络流算法，时间复杂度为O(V^2*E)。 - **HLPP最大流**：采用Hopcroft-Karp启发式算法，时间复杂度为O(V^3)。 - **最小费用流**：在满足流约束的同时最小化总费用，有不同的时间复杂度优化版本。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集**（点连通度）：涉及网络流的优化问题，如最小费用或最大化流量。 - **最小路径覆盖**：找到覆盖所有顶点的最小路径集合，时间复杂度为O(N^3)。 - **最小点集覆盖**：寻找覆盖所有边的最小顶点集合。 3. **Structure数据结构** - **求某天是星期几**：基于日期计算星期的方法。 - **左偏树**：一种特殊的二叉堆，合并复杂度为O(LOGN)。 - **树状数组**：用于高效地处理区间更新和查询问题。 - **二维树状数组**：扩展树状数组以处理二维数组的查询和更新。 - **TRIE树**：前缀树，用于高效存储和查找字符串。 - **后缀数组**：用于快速查找字符串的后缀，有O(N*LOGN)和O(N)两种构造方法。 - **RMQ**（Range Minimum Query）：求给定区间内的最小值，离线算法的时间复杂度为O(N*LOGN)+O(1)。 这些算法和数据结构是ACM竞赛中的核心，掌握它们能帮助参赛者解决各种复杂的编程问题。