ACM算法模板：吉林大学计算机科学与技术学院资源分享

"ACM算法模板(吉林大学)" 是一份由吉林大学计算机科学与技术学院2005级学生在2007-2008学年整理的算法参考资料，主要涵盖了图论、网络流和数据结构等多个方面的经典算法。 在图论部分，文档详细列举了多种算法实现，包括： 1. DAG的深度优先搜索标记，用于遍历无向图或有向无环图。 2. 无向图找桥，识别图中的关键连接。 3. 无向图连通度计算，确定图的连通分量。 4. 最大团问题，利用动态规划和DFS寻找图中的最大完全子图。 5. 欧拉路径算法，找到图中起点到终点的欧拉路径，如果有多个，则路径长度最小。 6. Dijkstra算法的两种实现，分别是基于数组的O(N^2)版本和基于优先队列的O(E*LOGE)版本，用于求解单源最短路径。 7. Bellman-Ford算法，解决含有负权边的单源最短路径问题。 8. SPFA算法，一种优化的Bellman-Ford算法，效率更高。 9. 第K短路问题，Dijkstra和A*算法的变种，找到起点到其他点的第K条最短路径。 10. Prim算法，用于构造最小生成树。 11. 次小生成树算法，寻找次优的最小生成树。 12. 最小生成森林问题，利用Kruskal或Prim算法解决，这里提到的实现为O(MLOGM)时间复杂度。 13. 有向图最小树形图，构建最小树形图的问题。 14. Tarjan算法，用于检测强连通分量。 15. 弦图的判断及完美消除点排列，处理弦图相关问题。 16. 稳定婚姻问题，应用Gale-Shapley算法寻找稳定匹配。 17. 拓扑排序，对有向无环图进行排序。 18. 无向图和有向图的连通分支查找，以及有向图的强连通分支检测。 19. 有向图的最小点基计算，用于优化图的表示。 20. Floyd算法，求解所有顶点之间的最短路径。 21. 2-SAT问题，解决满足性问题的一种特殊形式。 在网络流部分，文档涵盖了各种网络流算法： 1. 匈牙利算法，用于求解二分图的最大匹配，有DFS和BFS两种实现方式。 2. Kuhn-Munkres算法，高效解决二分图最佳匹配问题。 3. 无向图最小割，找到将图分成两个独立集合的最小代价割。 4. 有上下界约束的最小（最大）流问题。 5. Dinic算法，解决最大流问题，时间复杂度为O(V^2*E)。 6. HLPP算法，另一种求解最大流的方法，时间复杂度为O(V^3)。 7. 最小费用流算法，考虑流的费用，同时最大化流量和最小化总费用。 8. 最小费用流的另一种实现，时间复杂度为O(V^2*F)。 9. 最佳边割集和最佳点割集，寻找具有最优属性的割。 10. 最小边割集和最小点割集，分别针对边和点的连通度问题。 11. 最小路径覆盖问题，寻找覆盖所有边的最小路径集合。 12. 最小点集覆盖，寻找覆盖所有边的最小顶点集合。 在数据结构部分，文档包含了： 1. 求某天是星期几的算法，可能涉及到日期处理。 2. 左偏树，一种特殊的二叉堆，其合并复杂度为O(LOGN)。 3. 树状数组，用于高效地执行区间更新和查询操作。 4. 二维树状数组，扩展了树状数组以处理二维数据。 5. Trie树，又称前缀树，用于存储和检索字符串数据。 6. 后缀数组，用于快速查找字符串的后缀，有O(N*LOGN)和O(N)两种构建方法。 7. RMQ（Range Minimum Query），查询区间内最小值的问题，这里有离线算法O(N*LOGN)+O(1)。 这份资源为ACM竞赛选手和对算法感兴趣的开发者提供了丰富的参考资料，涵盖了图论、网络流和数据结构等多个重要领域，对于理解和实现这些经典算法非常有帮助。