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

"该资源是一个ACM/ICPC竞赛编程的代码库，包含了jojer和Fandywang两位作者整理的算法模板，主要涵盖图论、网络流和数据结构等方面的知识，旨在帮助参赛者快速解决各类算法问题。" 在这个代码库中，关于图论的算法模板包括： 1. DAG的深度优先搜索标记：用于处理有向无环图(DAG)的遍历和标记。 2. 无向图找桥：寻找图中的桥，即删除某条边后导致连通性改变的边。 3. 无向图连通度(割)：计算无向图的连通分量数量，以及最小割。 4. 最大团问题：使用动态规划和DFS求解图中的最大完全子图。 5. 欧拉路径：找到图中的欧拉路径，即经过每条边恰好一次的路径。 6. Dijkstra算法的两种实现：一种是简单的数组实现，时间复杂度为O(N^2)，另一种是优化后的版本，时间复杂度为O(E*LOGE)。 7. Bellman-Ford算法：求解图中的单源最短路径，时间复杂度为O(VE)。 8. SPFA算法：Shortest Path Faster Algorithm，用于求解单源最短路径。 9. 第K短路：分别用Dijkstra和A*算法求解。 10. Prim算法：求解最小生成树，时间复杂度为O(MLOGM)。 11. 次小生成树：另一种求最小生成树的方法，时间复杂度为O(V^2)。 12. 最小生成森林：处理多棵树的最小生成树问题。 13. 有向图最小树形图：求解有向图的最小树形图问题。 14. Tarjan算法：用于寻找图中的强连通分量。 15. 弦图的判断和完美消除点排列：处理弦图的特定性质。 16. 稳定婚姻问题：基于Gale-Shapley算法求解稳定婚姻分配问题。 在网络流部分，涉及的算法包括： 1. 二分图匹配：三种不同的实现方式，匈牙利算法的DFS和BFS实现，以及HOPCROFT-CARP算法。 2. Kuhn-Munkres算法：求解二分图的最佳匹配，时间复杂度为O(M*M*N)。 3. 无向图最小割：计算图的最小割，用于分离网络。 4. 有上下界限制的最小(最大)流问题。 5. Dinic算法：求解最大流问题，时间复杂度为O(V^2*E)。 6. HLPP算法：Highway-Linkage-Path-Push-Relabel的最大流算法，时间复杂度为O(V^3)。 7. 最小费用流：同时考虑流量和费用的网络流问题，有两种不同复杂度的实现。 8. 最佳边割集、最佳点割集和最小边/点割集：与网络流相关的割集优化问题。 9. 最小路径覆盖：寻找图中最小的路径集合，覆盖所有顶点。 10. 最小点集覆盖：寻找最小的点集合，使得每个边至少有一个端点在集合中。 最后，数据结构方面： 1. 求某天是星期几：根据日期计算星期。 2. 左偏树：一种特殊的二叉堆，具有合并操作的低复杂度。 3. 树状数组：用于快速查询和更新区间加法的数组结构。 4. 二维树状数组：扩展树状数组到二维情况，处理二维区间加法。 5. TRIE树：前缀树，用于高效存储和查找字符串。 6. 后缀数组：处理字符串的后缀，有O(N*LOGN)和O(N)两种构建方法。 7. RQ(Range Minimum Query)：区间最小值查询，离线算法实现为O(N*LOGN)+O(1)。 这些算法模板对于ACM/ICPC比赛和算法学习者来说是非常宝贵的资源，可以帮助他们在短时间内理解和实现各种复杂算法。