"吉林大学ACM/ICPC 代码库包含了大量的算法和数据结构实现,主要针对ACM/ICPC竞赛中的常见问题,如图论、网络流、数据结构等。这个代码库由吉林大学计算机科学与技术学院2005级的学生创建并维护,经过多次修订,包括Fandywang1在内的多位贡献者参与了更新。"
本文将详细解析此代码库中涉及的知识点:
1. **Graph图论**
- **DAG的深度优先搜索标记**:在有向无环图(DAG)中,使用DFS遍历所有节点并进行标记,通常用于拓扑排序或寻找关键路径。
- **无向图找桥**:查找图中的桥(断点),桥是使得图不连通的边。
- **无向图连通度**:计算图的连通分量,确定图中最大的连通子图。
- **最大团问题**:寻找图中最大的完全子图,即每个节点都与其他所有节点相连的子图,可使用动态规划+DFS求解。
- **欧拉路径**:找到一条经过图中每条边恰好一次的路径,O(E)表示线性时间复杂度的解决方案。
- **DIJKSTRA算法**:求解单源最短路径问题,有数组实现的O(N^2)版本和优化后的O(E*LOGE)版本。
- **BELLMAN-FORD算法**:处理负权边的单源最短路径问题,时间复杂度为O(VE)。
- **SPFA算法**:Shortest Path Faster Algorithm,一种基于队列的最短路径算法,适用于负权边。
- **第K短路**:寻找除了最短路径外的第K短路径,可以使用DIJKSTRA或A*算法进行扩展。
- **PRIM算法**:求解最小生成树,用于无向图,时间复杂度O(V^2)。
- **次小生成树**:找到第二小的生成树,一般使用Kruskal或Prim算法的变种。
- **最小生成森林问题**:处理带有多棵树的最小生成树问题,可以使用Prim或Kruskal算法。
- **有向图最小树形图**(最小生成树的有向版本)。
- **TARJAN强连通分量**:检测图中的强连通组件,即任意两个节点之间都有路径可达的子图。
- **弦图判断及完美消除序列**:弦图是一类特殊的图,可以通过特定的点排列进行判断。
- **稳定婚姻问题**:Gale-Shapley算法解决,寻找一个稳定的匹配方案,时间复杂度O(N^2)。
- **拓扑排序**:对有向无环图进行排序,使得对于每条边(u, v),u总是在v之前。
- **无向图连通分支**:使用DFS或BFS检测图的连通分支。
- **有向图强连通分支**:检测有向图的强连通组件,DFS或BFS邻接矩阵实现。
- **有向图最小点基**:寻找最小的点集,使得图中每条边都指向该集合内的至少一个点。
2. **Network网络流**
- **二分图匹配**:匈牙利算法(DFS和BFS实现)以及HOPCROFT-CARP算法,用于寻找二分图中的最大匹配。
- **KUHNMUNKRAS算法**:高效求解二分图的最佳匹配,时间复杂度为O(M*M*N)。
- **无向图最小割**:寻找图中最小的割,使得割两边的顶点不连通,时间复杂度O(N^3)。
- **有上下界最小(最大)流**:处理具有流量上限和下限的网络流问题。
- **DINIC算法**:求解最大流问题,时间复杂度O(V^2*E)。
- **HLPP算法**:霍尔夫曼-普拉特-普拉特算法,用于最大流问题,时间复杂度O(V^3)。
- **最小费用流**:考虑每条边的费用,找到总费用最小的流,有多种实现方法,如O(V*E*F)和O(V^2*F)。
- **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集**(点连通度):这些是网络流问题的变种,用于寻找不同类型的最优割。
- **最小路径覆盖**:找到覆盖所有边的最小路径集合,时间复杂度O(N^3)。
- **最小点集覆盖**:找到覆盖所有边的最小顶点集合。
3. **Structure数据结构**
- **求某天是星期几**:根据日期计算星期,可能涉及到日期处理和模运算。
- **左偏树**:一种自平衡二叉查找树,其合并操作的时间复杂度为O(LOGN)。
- **树状数组**(也称作线段树):用于高效地处理区间查询和修改,常用于求和问题。
这些算法和数据结构是ACM/ICPC竞赛中常见的挑战,理解和掌握它们对于提高编程竞赛能力至关重要。吉林大学的代码库提供了一个宝贵的实践和学习资源,帮助参赛者深入理解并应用这些理论知识。