吉林大学ACM算法模板：从图论到网络流详解

ACM/ICPC算法模板是一份针对吉林大学计算机科学与技术学院2005级学生编写的教学资料，旨在帮助学习C语言和数据结构的学生掌握解决ACM竞赛中常见问题的算法技巧。这份模板涵盖了广泛的ACM算法领域，包括但不限于图论、网络流、数据结构等多个核心模块。 在图论部分，它详细讲解了： 1. **DAG深度优先搜索标记**：利用DFS探索有向无环图（DAG）的节点，用于标记和遍历。 2. **无向图的桥和连通度**：通过寻找割点和边来确定图的连通性和关键路径。 3. **最大团问题（DP+DFS）**：使用动态规划和深度优先搜索找到最大团的数量。 4. **欧拉路径和迪杰斯特拉算法**：欧拉路径关注所有边恰好一次的路径，迪杰斯特拉用于求解单源最短路径问题，有O(N^2)和O(E*LOGE)两种实现。 5. **贝尔曼-福德算法**：用于单源最短路径，即使图中存在负权边也能处理。 6. **SPFA（最短路径更快算法）**：一种优化过的SPF算法，适用于稠密图。 7. **第K短路（DIJKSTRA和A*）**：分别探讨了基于距离和启发式搜索的寻找最短路径方法。 8. **Prim算法**：用于寻找最小生成树，具有O(V^2)的时间复杂度。 9. **最小生成森林问题**：找到多个树覆盖所有顶点，时间复杂度为O(MLOGM)，其中M是边的数量。 10. **有向图最小树形图**：构建有向图的最小树结构。 11. **最小斯坦纳树**：在带权重的无向图中找到一棵连接所有顶点的树，使其总权重最小。 12. **TARJAN强连通分量**：用于识别图中的强连通分量。 13. **弦图判断与完美消除点排列**：分析图的特殊结构。 14. **稳定婚姻问题**：经典的婚配问题，用匈牙利算法解决。 15. **拓扑排序**：对有向无环图进行排序，确保依赖关系的正确性。 16. **图的连通分支**：使用DFS或BFS遍历无向图的连通分支。 在网络流部分，涉及： - **二分图匹配算法**：包括匈牙利算法的DFS和BFS实现，以及Hopcroft-Karp算法。 - **最小割问题**：计算无向图的最小割，有O(N^3)的方法。 - **最大流算法**：如Dinic的O(V^2*E)算法和HLPP的O(V^3)算法，以及最小费用流算法。 - **最佳边割集和点割集**：涉及不同类型的割集查找。 - **最小路径覆盖和点集覆盖**：查找特定条件下的覆盖集合。 数据结构部分涵盖： - **日期转换为星期几**：基础的日期计算问题。 - **树状数组和二维树状数组**：高效的数据查询结构。 - **Trie树**：多叉树和特定结构的查找。 - **后缀数组**：字符串处理中的高效工具，有O(N*LOGN)和O(N)的不同实现。 - **区间查询**：通过RMQ离线算法，提供O(N*LOGN)预处理时间和O(1)查询时间。 这份模板为ACM竞赛参与者提供了强大的理论支持和实践指导，有助于提升参赛者的算法设计和解决问题的能力。