吉林大学ACM代码库：C/C++实现算法集

"吉林大学ACM常用代码库包含C/C++编写的ACM竞赛相关算法，虽然注释较少，但涵盖了图论、网络流、数据结构等多个重要领域。" 这篇资源是一个C/C++编程的代码库，专为ACM(国际大学生程序设计竞赛)竞赛准备。ACM竞赛主要考验参赛者的算法设计、编程能力和问题解决技巧。这个代码库由吉林大学计算机科学与技术学院2005级的学生创建和维护，并在后续年份进行了修订。 1. **Graph图论**： - **DAG的深度优先搜索标记**: 在有向无环图(DAG)中，通过深度优先搜索进行节点标记，用于查找特定路径或结构。 - **无向图找桥**: 找到无向图中的桥，即删除后会导致图分块的边。 - **无向图连通度(割)**: 计算无向图的连通分量个数，即最大独立集合。 - **最大团问题**：寻找无向图中最大的完全子图，可以使用动态规划和深度优先搜索相结合的方法。 - **欧拉路径**：找到起点和终点间包含所有边的路径，适用于具有欧拉路径的图。 - **DIJKSTRA算法**：求解单源最短路径，这里提到了两种实现方式：数组实现和优化后的版本。 - **BELLMAN-FORD算法**：处理含有负权边的单源最短路径问题。 - **SPFA算法**：短路径更快算法，是求解单源最短路径的一种方法。 - **第K短路**：不仅求最短路，还考虑了第K短的路径，两种方法分别基于DIJKSTRA和A*算法。 - **PRIM算法**：求最小生成树，用于无向图。 - **次小生成树**：寻找第二小的生成树，通常使用Kruskal或Prim的变种。 - **最小生成森林问题**：处理有向图的最小树形图问题，可能涉及多棵最小生成树。 - **TARJAN强连通分量**：检测有向图中的强连通分量，即图中任何两点间都存在双向路径的子图。 - **弦图判断**及**PERFECT ELIMINATION点排列**：弦图理论在图论中有特定应用，如完美消除序等。 - **稳定婚姻问题**：利用Gale-Shapley算法解决匹配问题，保证稳定性。 - **拓扑排序**：对有向无环图进行线性排序。 - **无向图连通分支**：通过DFS或BFS找到图的连通分支。 - **有向图强连通分支**：找出有向图的强连通分量。 - **有向图最小点基**：寻找图中最小的点集，使得任意一条边连接两个不在集合内的点。 - **FLOYD算法**：求解所有顶点间的最短路径，允许负权重。 - **2-SAT问题**：满足2-CNF布尔公式的问题，是SAT问题的一个特殊子类。 2. **Network网络流**： - **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及HOPCROFT-KARP算法，用于寻找二分图的最佳匹配。 - **无向图最小割**：寻找将图分割成两部分的最小代价边集合。 - **有上下界的最小(最大)流**：在网络流问题中，考虑流量的上下界限制。 - **DINIC算法**：求解最大流，时间复杂度为O(V^2*E)。 - **HLPP最大流算法**：赫尔曼-利普奇茨-普拉特算法，时间复杂度为O(V^3)。 - **最小费用流**：同时考虑流量和费用，寻找最小总费用的最大流。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集（点连通度）**：涉及网络流中的割集优化问题。 - **最小路径覆盖**：寻找覆盖所有边的最小路径集合。 - **最小点集覆盖**：在图中找到最小的点集合，使得每个边至少有一个端点在集合内。 3. **Structure数据结构**： - **求某天是星期几**：可能涉及到日期计算和转换。 - **左偏树**：一种自平衡二叉查找树，常用于实现高效的数据结构操作。 - **其他数据结构相关的算法和实现**：由于描述不完整，这部分可能包括栈、队列、树、堆、哈希表等各种常见数据结构及其应用。 这个代码库提供了丰富的ACM竞赛中常见的算法实现，对于学习和参赛者来说是一份宝贵的参考资料。尽管注释可能较少，但通过阅读和理解代码，可以深入掌握这些基础和高级算法。