吉林大学ACM团队代码库：图论与数据结构精华

"这份文档是吉林大学ACM/ICPC代码库，主要包含了各种算法和数据结构的实现，适用于对ACM竞赛有兴趣的学习者。文档详细记录了不同算法的复杂度和应用，如图论中的最小费用流、最佳边割集、最小点割集等，以及数据结构如树状数组、后缀数组、Trie树等。" 在ACM竞赛中，掌握高效算法和数据结构至关重要。这份文档涵盖了以下几个方面的知识点： 1. **图论**： - **最小费用流**：提供两种实现，一种是O(V^2*F)，另一种是O(V^2*F)，其中V代表顶点数量，E表示边的数量，F是流量上限。 - **最佳边割集**和**最佳点割集**：这些是图的割相关的概念，用于寻找能最大化或最小化某种目标的割。 - **最小边割集**和**最小点割集（点连通度）**：这两种割集计算是图连通性分析的一部分。 - **最小路径覆盖**和**最小点集覆盖**：涉及图的覆盖问题，寻找最少的路径或点集合以覆盖所有节点。 2. **最短路径算法**： - **Dijkstra算法**：提供了两种实现，一个是基于数组的O(N^2)版本，另一个是优化后的O(E*LOGE)版本。 - **Bellman-Ford算法**：用于处理有负权边的最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：Shortest Path Faster Algorithm，一种改进的Dijkstra算法，适用于处理负权边。 - **第K短路**：使用Dijkstra和A*两种方法求解，分别适用于没有启发式信息和有启发式信息的情况。 3. **最小生成树算法**： - **Prim算法**：求解无向图的最小生成树，时间复杂度为O(V^2)。 - **次小生成树**：找到第二小的生成树，时间复杂度为O(V^2)。 - **最小生成森林问题**：处理多棵树的最小生成树，使用Kruskal或Prim算法，这里给出的是O(MLOGM)的解法。 - **有向图最小树形图**：在有向图中找到最小树形图，即最小生成树的有向版本。 4. **图的其他算法**： - **TARJAN强连通分量**：用于识别有向图中的强连通组件。 - **弦图判断**和**弦图的PERFECT ELIMINATION点排列**：弦图是一种特殊的图，具有特定的性质。 - **稳定婚姻问题**：一个著名的组合优化问题，可以使用Gale-Shapley算法解决。 5. **数据结构**： - **求某天是星期几**：涉及到日期和日历算法。 - **左偏树**：一种自平衡二叉查找树，其合并操作的时间复杂度为O(LOGN)。 - **树状数组**：用于动态维护区间和或区间更新。 - **二维树状数组**：扩展了树状数组，处理二维区间问题。 - **Trie树**：又称前缀树，用于高效地存储和检索字符串。 - **后缀数组**：用于处理字符串的后缀，有O(N*LOGN)和O(N)两种构建方法。 - **RMQ（Range Minimum/Maximum Query）**：询问区间内最小或最大值的问题，离线算法有O(N*LOGN)+O(1)的复杂度。 - **LCA（Lowest Common Ancestor）**：求解树中两点的最近公共祖先，离线算法有O(E)+O(1)的复杂度。 - **带权值的并查集**：支持合并和查询操作，并考虑了权重因素。 - **快速排序**：经典的排序算法，平均时间复杂度为O(NLOGN)。 - **2台机器工作调度**：优化任务分配以最小化完成时间的算法。 这些内容对于参加ACM竞赛或者提升算法能力的程序员来说是非常宝贵的资源，提供了大量实战经验总结和高效的解决方案。