吉林大学ACM算法与数据结构模板

"吉林大学ACM模板是一个包含各种经典算法和数据结构的代码库，主要针对ACM/ICPC竞赛，由jojer&Fandywang创建，来自吉林大学计算机科学与技术学院2005级。这个模板涵盖了图论、计算几何、动态规划和数据结构等多个领域的问题解决方法。" 在图论部分，模板提供了以下算法： 1. DAG的深度优先搜索标记，用于处理有向无环图的遍历。 2. 无向图找桥，用于识别图中的关键边，这些边移除后会使得图不再连通。 3. 无向图连通度(割)，计算图的连通分量数量。 4. 最大团问题，通过动态规划和DFS寻找图中最大的完全子图。 5. 欧拉路径的O(E)时间复杂度算法，用于找出图中的欧拉路径。 6. Dijkstra算法的数组实现，O(N^2)时间复杂度，求解单源最短路径。 7. Dijkstra算法的优化版本，O(E*LOGE)时间复杂度。 8. Bellman-Ford算法，O(VE)时间复杂度，求解单源最短路径，支持负权边。 9. SPFA（Shortest Path Faster Algorithm），一种快速求解单源最短路径的算法。 10. 第K短路算法，通过Dijkstra或A*算法实现。 11. Prim算法，用于求解最小生成树。 12. 次小生成树，O(V^2)时间复杂度，找到第二小的生成树。 13. 最小生成森林问题，利用Prim或Kruskal算法，O(MLOGM)时间复杂度，解决多源最短路径问题。 14. 有向图最小树形图，与最小生成树类似，但适用于有向图。 15. Tarjan算法，用于求解强连通分量。 16. 弦图的判断和完美消除点排列，处理图的特定性质。 17. 稳定婚姻问题，O(N^2)时间复杂度，基于Gale-Shapley算法。 18. 拓扑排序，对有向无环图进行排序。 19. 无向图和有向图的连通分支计算，使用DFS或BFS邻接矩阵实现。 20. 有向图的最小点基，求解图的基，O(N^2)时间复杂度。 21. Floyd算法，用于求解所有对之间的最短路径。 22. 2-SAT问题，解决满足性问题。 在网络流部分，模板包含了： 1. 二分图匹配，通过匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp算法。 2. Kuhn-Munkres算法，求解二分图的最佳匹配，O(M*M*N)时间复杂度。 3. 无向图最小割，O(N^3)时间复杂度。 4. 有上下界限制的最小(最大)流问题。 5. Dinic算法，求解最大流，O(V^2*E)时间复杂度。 6. HLPP算法，另一种求解最大流的方法，O(V^3)时间复杂度。 7. 最小费用流，包括两种不同复杂度的实现，O(V*E*F)和O(V^2*F)。 8. 最佳边割集和最佳点割集问题。 9. 最小边割集和最小点割集，与点连通度有关。 10. 最小路径覆盖问题，O(N^3)时间复杂度。 11. 最小点集覆盖，用于减少集合的大小。 在数据结构部分，模板涵盖： 1. 求某天是星期几的算法，处理日期计算。 2. 左偏树，高效合并，复杂度O(LOGN)。 3. 树状数组，一种动态维护区间和的结构。 4. 二维树状数组，扩展树状数组以处理二维区间问题。 5. Trie树，用于字符串搜索和压缩存储，包括K叉和左儿子右兄弟两种实现。 6. 后缀数组，用于字符串操作，有O(N*LOGN)和O(N)两种构建方法。 7. RMQ（Range Minimum Query），求解区间最小值，离线算法O(N*LOGN)+O(1)。 这个模板全面且深入，适合ACM竞赛选手以及需要高效算法和数据结构的开发者参考。