吉林大学ACM/ICPC算法模板库

"吉林大学ACM/ICPC模板是一个由吉林大学计算机科学与技术学院2005级学生创建并维护的代码库，主要用于ACM/ICPC竞赛的算法准备。该模板涵盖了图论、数论、几何、数据结构和动态规划等多个领域的算法模板，帮助参赛者快速理解和实现常见问题的解决方案。文档中详细列举了各种算法的实现，包括但不限于图的深度优先搜索、最短路径计算、最小生成树、网络流等问题。" 在ACM/ICPC模板中，关于图论的部分非常详尽，包括但不限于以下算法： 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，一种基于队列的改进版Bellman-Ford算法，用于求解单源最短路径。 9. **第K短路**：除了最短路径外，还可以找到第二、第三等最短路径，可以通过Dijkstra或A*算法进行扩展。 10. **Prim算法**：求解最小生成树，时间复杂度为O(V^2)，适用于稠密图。 11. **最小生成森林**：处理多棵最小生成树的情况，可以使用Kruskal算法或改进后的算法，如O(M*logM)的时间复杂度。 12. **有向图最小树形图**：在有向图中找到最小树形图，即最小的树形子图连接所有顶点。 13. **TARJAN强连通分量**：检测有向图中的强连通分量，即从任何顶点都能到达其他所有顶点的子图。 14. **弦图**：处理弦图的判断及其完美消除序列，以及稳定婚姻问题。 15. **拓扑排序**：对DAG进行排序，使得对于每条有向边(u, v)，u都在v之前。 16. **最小环查找**：Floyd算法可以用于寻找图中的最小环。 数据结构方面，包括但不限于： 1. **求某天是星期几**：可能涉及到日期计算和星期的循环。 2. **左偏树**：一种特殊的二叉堆，保证左孩子总是大于或等于右孩子，用于高效地处理某些操作。 此外，模板还涉及了网络流算法，如匈牙利算法实现的二分图匹配、Kuhn-Munkres算法、Dinic算法和 HLPP 算法等，以及最小费用流问题的解决方法。 这些模板为ACM/ICPC参赛者提供了一个全面的参考框架，方便他们快速理解和实现各种算法，提高解决问题的效率。