ACM竞赛算法模板：吉林大学版

"ACM算法模板(吉林大学) icpc ACM竞赛试题模板，acm经典算法" ACM/ICPC算法模板是针对国际大学生程序设计竞赛（ACM/ICPC）准备的一系列常用算法集合，主要涵盖了图论、网络流、数据结构等多个核心领域。这份模板来自吉林大学计算机科学与技术学院2005级，旨在帮助参赛者快速理解和应用关键算法。 1. 图论： - DAG的深度优先搜索标记：用于识别有向无环图（DAG）中的特定路径或状态。 - 无向图找桥：检测无向图中的桥，即删除后导致连通性改变的边。 - 无向图连通度（割）：计算图的连通分量数量，了解其分割情况。 - 最大团问题：寻找图中最大的完全子图，所有节点之间两两相连。 - 欧拉路径：找出图中从一个顶点出发并经过每条边一次且仅一次的路径。 - Dijkstra算法：求解单源最短路径问题，有两种实现，一种是数组实现，时间复杂度为O(N^2)，另一种是优先队列优化后的实现，时间复杂度为O(E log E)。 - Bellman-Ford算法：解决具有负权边的单源最短路径问题，时间复杂度为O(VE)。 - SPFA（Shortest Path Faster Algorithm）：一种近似最短路径算法，适用于负权边的情况。 - 第K短路：不仅找到最短路径，还能找到第K短的路径，可使用Dijkstra或A*算法扩展。 - Prim算法：构造最小生成树，时间复杂度为O(V^2)。 - 次小生成树：找到第二小的生成树，通常使用Kruskal或Prim的变种。 - 最小生成森林：解决多棵树的最小生成树问题，时间复杂度为O(M log M)。 - 最小树形图：有向图的最小树形图问题，与最小生成树类似。 - Tarjan算法：用于计算强连通分量，识别图中的循环结构。 - 弦图及其完美消除点排列：处理弦图的特殊性质，例如在弦图中寻找特定排列。 - 稳定婚姻问题：应用Gale-Shapley算法解决匹配问题，确保稳定性。 2. 网络流： - 二分图匹配：匈牙利算法通过DFS或BFS实现，寻找二分图的最大匹配。 - Kuhn-Munkres算法：优化二分图匹配，时间复杂度为O(M*M*N)。 - 最小割：在无向图中找到一个割，使得割两边的节点数乘积最小。 - 有上下界限制的最小(最大)流：处理流量有上限和下限的网络流问题。 - Dinic算法：求解最大流问题，时间复杂度为O(V^2*E)。 - HLPP算法：高效最大流算法，时间复杂度为O(V^3)。 - 最小费用流：同时考虑路径费用和流量，寻找最小总费用的流。 - 最佳边割集和最佳点割集：寻找具有最优属性的割。 - 最小边割集和最小点割集：分别找到最小的边集和点集以分割图。 3. 数据结构： - 求某天是星期几：根据日期计算星期。 - 左偏树：一种特殊的二叉堆，合并操作的时间复杂度为O(log N)。 - 树状数组：快速处理区间查询和更新的问题。 - 二维树状数组：扩展树状数组以支持二维区间操作。 - Trie树：用于高效存储和查找字符串的前缀，有K叉和左儿子右兄弟两种实现方式。 - 后缀数组：处理字符串后缀的排序，可以在线性和次线性时间复杂度内构建。 - RMQ（Range Minimum Query）：求解区间内的最小值，有在线和离线算法，离线版本预处理后常数时间内查询。 这些算法模板是ACM/ICPC竞赛准备的重要参考资料，对于提升算法能力和解决实际问题具有很高的价值。掌握这些算法，不仅可以应对比赛，还能为日常的编程工作打下坚实基础。