ACM竞赛算法集锦：吉林大学版

"这份资源是关于ACM竞赛中常用的算法模板，主要来自吉林大学计算机科学与技术学院2005级2007-2008年的代码库，包括了图论、网络流和数据结构等多个方面的问题解决方法。" 在ACM/ICPC竞赛中，图论算法占据了重要地位。目录中的"Graph图论"部分涵盖了多种经典算法： 1. **DAG的深度优先搜索标记**：用于处理有向无环图（DAG）的遍历。 2. **无向图找桥**：查找图中的桥（关键边），这些边移除后会增加连通分量的数量。 3. **无向图连通度(割)**：计算图的连通性，找出最大的不连通子图。 4. **最大团问题DP+DFS**：寻找图中最大的完全子图，即所有顶点两两之间都有边相连。 5. **欧拉路径O(E)**：找到图中一个起点到终点的路径，使得经过每条边恰好一次。 6. **DIJKSTRA算法**：两种实现，分别是O(N^2)的数组实现和O(E*LOGE)的优化版本，用于求解单源最短路径问题。 7. **BELLMAN-FORD单源最短路O(VE)**：处理带有负权边的单源最短路径问题。 8. **SPFA（SHORTEST PATH FASTER ALGORITHM）**：一种快速但不一定是最优的单源最短路径算法。 9. **第K短路**：除了最短路径外，还计算第K短的路径，分别使用DIJKSTRA和A*算法实现。 10. **PRIM求最小生成树**：Prim算法用于求解加权无向图的最小生成树。 11. **次小生成树O(V^2)**：求解加权无向图的第二小生成树。 12. **最小生成森林问题**：通过Kruskal或Prim算法求解最小生成森林，这里有O(MLOGM)的时间复杂度版本。 13. **有向图最小树形图** 和 **MINIMAL STEINERTREE**：与最小生成树类似，但在有向图上的应用。 14. **TARJAN强连通分量**：检测图中的强连通分量，即每个顶点都可以到达其他所有顶点的子图。 15. **弦图判断与PERFECT ELIMINATION点排列**：识别弦图并找到其完美消除顺序，相关于图的矩阵运算。 16. **稳定婚姻问题O(N^2)**：利用Gale-Shapley算法解决稳定匹配问题。 17. **拓扑排序**：对有向无环图进行排序，使得对于每一条有向边(u, v)，u都在v之前。 18. **无向图连通分支** 和 **有向图强连通分支**：利用DFS或BFS找到图的连通分支或强连通分支。 在网络流问题中，包括了各种最大流和最小割算法： 1. **二分图匹配**：有匈牙利算法的DFS和BFS实现，以及HOPCROFT-CARP算法。 2. **KUHN-MUNKRAS算法**：用于求解二分图的最佳匹配，时间复杂度为O(M*M*N)。 3. **无向图最小割O(N^3)**：寻找图中的最小割，即将图分割成两个尽可能大的连通分量。 4. **有上下界的最小(最大)流**：在保证流量限制条件下求解最小流或最大流问题。 5. **DINIC最大流O(V^2*E)**：Dinic算法，用于求解最大流问题。 6. **HLPP最大流O(V^3)**：基于Hall's Theorem的算法，求解最大流问题。 7. **最小费用流**：在考虑边的费用的情况下，求解最大流问题，有两种实现，时间复杂度分别为O(V*E*F)和O(V^2*F)。 8. **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集（点连通度）**：针对不同条件下的最小割问题。 9. **最小路径覆盖O(N^3)**：找出覆盖所有边的最小数量的简单路径。 10. **最小点集覆盖**：寻找最小的点集合，使得每个边都至少有一个端点在集合中。 在数据结构部分，包括了： 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竞赛中解决问题的关键工具。