吉林大学ACM/ICPC代码库：图论与网络流算法集

"acm/icpc标准代码库" 这篇摘要介绍的是一个针对ACM/ICPC竞赛准备的代码库，由吉林大学计算机科学与技术学院2005级的团队创建并维护。这个代码库涵盖了图论、网络流、递归、计算几何、数论、数据结构等多个计算机科学的核心领域，旨在帮助参赛者准备比赛和提高编程能力。 ### 图论 图论部分包括了多种算法，如： - **DAG的深度优先搜索标记**：在有向无环图（DAG）中进行深度优先搜索，并进行标记处理。 - **无向图找桥**：寻找无向图中的桥，即那些删除后会导致图分成分的边。 - **无向图连通度(割)**：计算图的连通分量和割点。 - **最大团问题**：利用动态规划和DFS解决寻找图中最大完全子图的问题。 - **欧拉路径**：找到图中的欧拉路径，路径经过每条边恰好一次。 - **DIJKSTRA算法**：两种实现方式，数组实现和优化后的版本，分别用于求解单源最短路径问题。 - **BELLMAN-FORD算法**：用于求解单源最短路径，可以处理负权边。 - **SPFA算法**：改进的Bellman-Ford算法，更快地找到单源最短路径。 - **第K短路**：使用Dijkstra或A*算法求解图中第K短的路径。 - **PRIM算法**：用于找到无向图的最小生成树。 - **次小生成树**：找到比最小生成树稍大的生成树。 - **最小生成森林问题**：处理多棵树的最小生成树问题。 - **有向图最小树形图**：在有向图中构建最小树形图。 - **TARJAN强连通分量**：检测图中的强连通分量。 - **弦图判断及完美消除序**：处理弦图的特性并找到完美消除序。 - **稳定婚姻问题**：通过Gale-Shapley算法解决稳定匹配问题。 - **拓扑排序**：对有向无环图进行排序。 - **无向图连通分支**：使用DFS或BFS找到无向图的连通分支。 - **有向图强连通分支**：使用DFS或BFS找到有向图的强连通分支。 - **有向图最小点基**：找到图的最小点基。 ### 网络流 网络流部分涉及各种流算法： - **二分图匹配**：使用匈牙利算法（DFS和BFS实现）以及HOPCROFT-CARP算法求解。 - **KUHN-MUNKRAS算法**：用于求解二分图的最佳匹配，效率较高。 - **无向图最小割**：寻找无向图的最小割，即最小容量的边集合。 - **有上下界最小(最大)流**：处理有上下界流量限制的网络流问题。 - **DINIC算法**：求解最大流问题，复杂度为O(V^2*E)。 - **HLPP算法**：更高效的最大流算法，复杂度为O(V^3)。 - **最小费用流**：同时考虑费用和流量的网络流问题，有多种实现方法。 - **最佳边割集、最佳点割集、最小边割集、最小点割集（点连通度）**：寻找不同条件下的最优割集。 - **最小路径覆盖**：找到覆盖所有节点的最小路径集合。 - **最小点集覆盖**：找到覆盖所有边的最小顶点集合。 ### 数据结构 数据结构部分涵盖了一些基本和高级的数据结构问题： - **求某天是星期几**：根据给定日期计算星期。 - **左偏树**：一种特殊的平衡二叉堆，用于高效操作。 - **斐波那契堆**：一种高效的优先队列实现。 - **跳跃列表**：快速查找和插入的随机化数据结构。 - **Splay树**：自调整的二叉查找树，通过操作优化访问性能。 - **Trie（字典树）**：用于存储字符串集合，便于快速查询。 - **B树和B+树**：用于数据库和文件系统的高效索引结构。 - **红黑树**：自平衡的二叉查找树，保证操作复杂度为O(logN)。 这个代码库提供了丰富的算法实现，对于参加ACM/ICPC竞赛的程序员来说，是一个宝贵的参考资料，同时也是深入学习和实践算法的好工具。