"ACM经典代码代码库.pdf" 是一份由吉林大学ACM/ICPC团队编写的文档，包含了各种经典算法的实现，主要涵盖图论、网络流和数据结构等领域。
在图论部分，文档详细列举了多种图算法，如：
1. DAG的深度优先搜索标记：用于遍历有向无环图（DAG）并进行标记。
2. 无向图找桥：查找无向图中的桥，桥是删除后会将图分割成多块的边。
3. 无向图连通度：计算无向图的连通分量，判断是否为强连通图。
4. 最大团问题：寻找图中最大的完全子图，可以使用动态规划和DFS解决。
5. 欧拉路径：找到一个起点到终点经过所有边恰好一次的路径。
6. Dijkstra算法：求解单源最短路径，有数组实现和优化版本。
7. Bellman-Ford算法：处理负权边的单源最短路径问题。
8. SPFA（Shortest Path Faster Algorithm）：一种快速但可能有循环的最短路径算法。
9. 第K短路：寻找除了最短路径外的其他最短路径，可以使用Dijkstra或A*算法扩展。
10. Prim算法：求解加权无向图的最小生成树。
11. 次小生成树：找到第二小的生成树。
12. 最小生成森林：处理多棵树的最小生成树问题。
13. 弦图判断及完美消除序列：弦图是指在有向图中每条边都是一个顶点的入边和另一个顶点的出边，完美消除序列是弦图的一种特殊排列。
14. 稳定婚姻问题：Gale-Shapley算法解决分配问题，确保没有两个未匹配的顶点愿意相互匹配。
15. 拓扑排序：对有向无环图进行线性排序。
16. 无向图连通分支：通过DFS或BFS查找图的连通分支。
17. 有向图强连通分支：检测有向图的强连通分量。
18. 有向图最小点基：寻找图中最小的点集，使得每个顶点都有出边。
19. Floyd算法：求解所有顶点对之间的最短路径。
20. 2-SAT问题：解决满足2-CNF形式的布尔逻辑问题。
在网络流部分，文档包括了：
1. 二分图匹配：匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp和Kuhn-Munkres算法。
2. 无向图最小割：寻找能分割图的最小边集合。
3. 有上下界的最小（最大）流：处理带容量限制的网络流问题。
4. Dinic算法：求解最大流，具有O(V^2*E)的时间复杂度。
5. HLPP（Hochbaum-Lausen-Papadimitriou-Perles）算法：另一种最大流算法，时间复杂度为O(V^3)。
6. 最小费用流：在保证流量的同时，最小化总的费用，有两种不同的实现。
7. 最佳边割集、最佳点割集、最小边割集和最小点割集（点连通度）：寻找网络中的最优割集。
8. 最小路径覆盖：找到覆盖所有边的最小顶点集合。
9. 最小点集覆盖：寻找覆盖所有边的最小顶点子集。
在数据结构部分，文档涉及：
1. 求某天是星期几：可能涉及日期计算或日历算法。
2. 左偏树：一种自平衡二叉查找树。
这份文档是ACM竞赛选手和算法学习者的重要参考资料，涵盖了图论、网络流和数据结构等多个方面，对于理解和实践这些算法有着极大的帮助。
我的内容管理
展开
