吉林大学ACM代码库：算法模板与图论网络流解析

"ACM代码库.pdf" 这篇文档是关于ACM/ICPC竞赛编程的代码模板集合，由吉林大学计算机科学与技术学院2005级的ACMGroup1成员整理和修订。它包含了各种图论、网络流和数据结构的算法实现，对于准备参加ACM编程竞赛或者需要这些算法的程序员来说是一份宝贵的参考资料。 1. **Graph图论** - **DAG的深度优先搜索标记**: 这是一种在有向无环图(DAG)中进行遍历的方法，用于标记节点状态或寻找特定路径。 - **无向图找桥**: 在无向图中，桥是指删除后会导致图不连通的边。 - **无向图连通度(割)**: 计算图的连通分量，了解图的最大独立集合或最小割。 - **最大团问题DP+DFS**: 使用动态规划和深度优先搜索求解图中的最大完全子图（最大团）。 - **欧拉路径**：确定一个图是否包含一条通过所有边且仅通过一次的路径。 - **DIJKSTRA算法**: 用于找到带权重的图中从源节点到其他所有节点的最短路径，有数组实现和优化后的实现。 - **BELLMAN-FORD算法**: 求解带负权边的图中单源最短路径问题。 - **SPFA算法**: 短est Path Faster Algorithm，一种解决单源最短路径问题的优化算法。 - **第K短路**: 找到图中第K条最短路径，可以基于Dijkstra或A*算法进行扩展。 - **PRIM算法**: 求解最小生成树(MST)，用于加权无向图。 - **次小生成树**: 找到加权无向图的第二小生成树。 - **最小生成森林问题**: 解决多棵树构成的最小生成森林。 - **有向图最小树形图**：在有向图中构建最小树形图的问题。 - **TARJAN算法**：用于检测图中的强连通分量。 - **弦图判断及完美消除点排列**：弦图是图论中的特殊结构，完美消除点排列有助于处理弦图问题。 - **稳定婚姻问题**：应用Gale-Shapley算法解决分配问题，确保没有两对人更愿意彼此配对。 - **拓扑排序**：在有向无环图中进行节点排序，使得每条边指向的节点都排在前面。 - **无向图连通分支**：使用DFS或BFS找出图的连通分支。 - **有向图强连通分支**：在有向图中找出强连通分量。 - **有向图最小点基**：找出图中最小的点集，使得每个点都可以到达其他所有点。 - **FLOYD算法**：用于求解所有节点之间的最短路径，可发现环。 2. **Network网络流** - **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及HOPCROFT-CARP算法，用于找到二分图中的最大匹配。 - **无向图最小割**：在无向图中找到一个割，使得割边的权重之和最小。 - **有上下界的最小(最大)流**：在网络流问题中考虑流量的上下界限制。 - **DINIC算法**：用于求解最大流问题，具有较高的效率。 - **HLPP算法**：Hierarchical Longest Path Pricipal，另一种求解最大流的方法。 - **最小费用流**：在考虑费用的情况下求解网络流问题，有多种实现优化时间和复杂度。 - **最佳边割集**、**最佳点割集**、**最小边割集**、**最小点割集（点连通度）**：这些涉及图的割集问题，寻找最优割集以满足特定条件。 3. **Structure数据结构** - **求某天是星期几**：计算给定日期对应的星期。 - **左偏树**：一种特殊的二叉堆，用于快速插入和查询操作。 这些代码模板涵盖了ACM竞赛中常见的算法和数据结构，对于提升编程能力，尤其是解决复杂问题的能力非常有帮助。通过学习和实践这些模板，参赛者可以提高解题速度和正确率。