ACM算法大全：图论、网络流与数据结构

"该资源是吉林大学ACM/ICPC代码库的一部分，包含了经典ACM竞赛中常用的代码和算法，涉及图论、网络流、数据结构等多个领域。这些代码适用于解决各种复杂问题，如图的深度优先搜索、最短路径、最小生成树、网络流优化等。" 本文将详细讲解这些ACM竞赛中常见的算法和知识点。 1. **图论** - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，深度优先搜索（DFS）用于标记节点的拓扑顺序或寻找关键路径。 - **无向图找桥**：桥是图中若去掉会增加连通分量的边，查找桥通常采用Tarjan算法或Kosaraju算法。 - **无向图连通度**：计算图的连通分支，可以通过DFS或BFS遍历来实现。 - **最大团问题**：寻找图中最大的完全子图，可以使用动态规划或DFS解决。 - **欧拉路径**：在欧拉图中，从任意点出发能通过每条边一次返回起点的路径。 - **Dijkstra算法**：用于找出图中从起点到各点的最短路径，有数组实现和优先队列实现两种方式。 - **Bellman-Ford算法**：处理带有负权边的最短路径问题。 - **SPFA算法**：一种优化的Bellman-Ford算法，处理最短路径问题。 - **第K短路**：寻找图中第K短的路径，可以基于Dijkstra或A*算法进行扩展。 - **Prim算法**：构建最小生成树，适用于无向图。 - **次小生成树**：找到第二小的生成树，可以使用Kruskal算法加上贪心策略。 - **最小生成森林**：对于多棵树构成的无向图，寻找最小生成森林，可使用Disjoint Set数据结构。 - **有向图最小树形图**：最小树形图问题，用于寻找有向图的最小生成树。 - **TARJAN强连通分量**：识别有向图中的强连通分量，利用深度优先搜索实现。 - **弦图判断与完美消除点排列**：弦图是一种特殊的图结构，完美消除点排列是解决弦图的一种方法。 - **稳定婚姻问题**：通过Gale-Shapley算法解决，保证稳定性。 2. **网络流** - **二分图匹配**：匈牙利算法（DFS和BFS实现）用于找到二分图的最大匹配。 - **HOPCROFT－CARP算法**：改进的二分图匹配算法。 - **Kuhn-Munkras算法**：用于找到二分图的最佳匹配，优化了时间复杂度。 - **无向图最小割**：寻找图中最小割，可应用在最大流问题中。 - **有上下界的最小(最大)流**：在网络流中考虑流量限制的上下界。 - **Dinic算法**：求解最大流问题，具有良好的性能。 - **HLPP算法**：Hopcroft-Karp Push-Relabel算法，用于求解最大流，时间复杂度更优。 - **最小费用流**：在考虑边权的情况下求解最大流问题，可以使用增广路径或迭代改进的方法。 - **最佳边割集**和**最佳点割集**：在满足特定条件下的最优割集选择。 - **最小边割集**和**最小点割集**（点连通度）：最小化割集大小以保持一定连通性。 - **最小路径覆盖**：寻找覆盖所有顶点的最小路径集合。 - **最小点集覆盖**：寻找覆盖所有边的最小顶点集合。 3. **数据结构** - **求某天是星期几**：根据格里高利历计算特定日期对应的星期。 - **左偏树**：一种自平衡的二叉堆，用于高效合并操作。 - **树状数组**：又称区间加查表，支持快速查询和更新区间元素的总和。 - **二维树状数组**：扩展树状数组以支持二维区间操作。 - **Trie树**：用于高效地存储和检索字符串，分为K叉和左儿子右兄弟两种实现。 - **后缀数组**：存储字符串所有后缀的排序数组，可用于模式匹配和最长公共前后缀等。 - **RMQ（Range Minimum/Maximum Query）**：在线或离线算法，用于查询给定区间内的最小或最大值。 - **LCA（Lowest Common Ancestor）**：最近公共祖先问题，离线算法可优化存储和查询效率。 - **带权值的并查集**：在并查集中引入权重，用于处理有权重的连通性问题。 - **快速排序**：高效的排序算法，平均时间复杂度为O(N log N)。 - **两台机器工作调度**：优化多任务分配以最小化完成时间。 - **大数运算**：包括高效的大数比较和普通的大数运算。 - **最长公共递增子序列**：找到两个序列中最长的公共递增子序列。 - **0-1分数规划**：线性规划的一种，其中变量取值为0或1。 - **最长有序子序列**：寻找递增或递减子序列的长度。 - **模线性方程**：在模意义下求解线性方程，如解模N的矩阵乘法。 - **模线性方程组**：同样在模意义下求解线性方程组。 - **筛素数**：高效地找出一定范围内的所有素数。 - **随机素数测试**：利用伪素数原理进行素数测试。 - **组合数学**：包括Polya计数、组合数C(N, R)等。 - **最大1矩阵**：寻找矩阵中1的最大个数。 - **约瑟夫环问题**：用数学方法或数组模拟解决。 - **取石子游戏**：博弈论问题，寻找最优策略。 - **集合划分问题**：将集合划分为子集合，满足特定条件。 以上是ACM常用代码库中涉及的关键知识点，这些算法和数据结构在解决实际问题和算法竞赛中具有重要作用。