"ACM经典代码库,包含吉林大学整理的ACM/ICPC竞赛相关的代码,旨在帮助对ACM编程竞赛感兴趣的人们"
本文档是吉林大学计算机科学与技术学院2005级2007-2008年整理的ACM/ICPC代码库,由jojer、sharang、xwbsw、Liuctic等人创建并由Fandywang在2008年10月进行了修订。这个代码库包含了大量与图论、网络流和数据结构相关的算法实现,是学习和研究ACM竞赛问题解决的重要资源。
**一、图论**
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算法**:较简单的最短路径算法,基于队列的数据结构,效率略高于BELLMAN-FORD。
9. **第K短路**:分别通过DIJKSTRA和A*算法来求解。
10. **PRIM算法**:求解加权无向图的最小生成树,时间复杂度为O(V^2)。
11. **次小生成树**:用其他方法求解最小生成树,如Kruskal算法,时间复杂度为O(MLOGM)。
12. **最小生成森林问题**:处理有向图的最小树形图,可能包含多棵最小生成树。
13. **TARJAN强连通分量**:找出图中的强连通分量。
14. **弦图判断**:识别图是否为弦图及其特性。
15. **弦图的PERFECT ELIMINATION点排列**:与弦图相关的特殊点排列问题。
16. **稳定婚姻问题**:应用Gale-Shapley算法求解稳定匹配问题,时间复杂度为O(N^2)。
17. **拓扑排序**:对有向无环图进行非唯一的线性排序。
18. **无向图连通分支**:通过DFS或BFS找到图的连通分支。
19. **有向图强连通分支**:同上,但针对有向图。
20. **有向图最小点基**:寻找图的最小点基,与图的连通性有关。
**二、网络流**
1. **二分图匹配**:包括匈牙利算法的DFS和BFS实现以及HOPCROFT-CARP算法。
2. **二分图最佳匹配**:KUHN-MUNKRAS算法求解,时间复杂度为O(M*M*N)。
3. **无向图最小割**:寻找将图分成两个部分的最小割。
4. **有上下界的最小(最大)流**:处理带容量限制的流问题。
5. **DINIC算法**:求解最大流,时间复杂度为O(V^2*E)。
6. **HLPP算法**:另一种最大流算法,时间复杂度为O(V^3)。
7. **最小费用流**:同时考虑流量和费用,有多种实现方法。
8. **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集(点连通度)**:涉及图的割问题,对网络流有重要应用。
9. **最小路径覆盖**:寻找覆盖所有节点的最小路径集合。
10. **最小点集覆盖**:寻找覆盖所有边的最小点集。
**三、数据结构**
1. **求某天是星期几**:可能涉及到日期处理和模运算。
2. **左偏树**:一种自平衡二叉查找树,适用于需要频繁插入操作的场景。
3. **其他未列出的数据结构实现**:可能包括堆、树、图、链表、队列、栈等常见数据结构的ACM竞赛应用。
这个代码库对于准备ACM/ICPC竞赛的程序员来说是一份宝贵的参考资料,涵盖了大量经典的算法和问题解决技巧,有助于提升算法设计和编程能力。