"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竞赛的程序员来说是一份宝贵的参考资料，涵盖了大量经典的算法和问题解决技巧，有助于提升算法设计和编程能力。
我的内容管理
展开
