ACM/ICPC算法代码集合：图论与网络流

"这个资源是一个ACM/ICPC竞赛相关的代码库，主要包含了各种图论、网络流和数据结构的算法实现，旨在帮助提升编程能力和解决竞赛中的算法问题。" 在ACM/ICPC竞赛中，熟悉并掌握一系列关键算法是至关重要的。此代码库涵盖了以下关键知识点： 1. **Graph图论**： - **DAG的深度优先搜索（DFS）标记**: 在有向无环图（DAG）中，DFS可以用来标记节点的访问状态，例如确定拓扑排序。 - **无向图找桥**: 桥是指在无向图中，如果移除该边会导致原本连通的两个子图变为不连通的边。 - **无向图连通度(割)**: 计算无向图的连通分量，评估图的连通性。 - **最大团问题**: 寻找图中最大的完全子图，所有节点间都有边相连。 - **欧拉路径**：在有向或无向图中寻找通过每个边恰好一次的路径。 - **Dijkstra算法**：用于求解单源最短路径问题，有两种实现方式：基于数组的O(N^2)实现和基于优先队列的O(E log E)实现。 - **Bellman-Ford算法**：处理带有负权边的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：一种改进的最短路径算法，适用于存在负权边的情况。 - **第K短路**：找到从源节点到其他节点的第K短路径，可以通过Dijkstra或A*算法进行扩展。 - **Prim算法**：求解最小生成树（MST），适用于加权无向图，时间复杂度为O(V^2)。 - **Kruskal算法**：另一种求MST的方法，适用于加权无向图，时间复杂度为O(M log M)，这里提到了次小生成树问题。 - **最小生成森林**：处理包含多棵MST的问题，可能涉及到Disjoint Set数据结构。 - **有向图最小树形图**（Minimal Steiner Tree）：在有向图中找到一棵包含特定节点集合的最小树形图。 - **Tarjan算法**：用于检测图中的强连通分量。 - **弦图判断及完美消除序**：在图理论中，弦图是一类特殊的图，可以应用于某些优化问题。 - **稳定婚姻问题**：用Gale-Shapley算法解决，O(N^2)的时间复杂度。 - **拓扑排序**：对DAG进行排序，使得对于每条有向边(u, v)，u的排序位置总是在v之前。 2. **Network网络流**： - **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp算法，目的是找到二分图中的最大匹配。 - **Kuhn-Munkres算法**：用于解决二分图的最佳匹配问题，具有O(M*M*N)的时间复杂度。 - **最小割**：在无向图中寻找最小的边集合，其移除会导致两部分节点不连通。 - **最大流**：寻找网络中从源点到汇点的最大流量，包括Dinic算法（O(V^2*E)）和 HLPP算法（O(V^3)）。 - **最小费用流**：在满足最大流的同时，最小化整个网络的总费用，有多种实现方法，如O(V*E*F)和O(V^2*F)。 - **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集（点连通度）**：这些都是在网络流问题中的特定割集优化问题。 - **最小路径覆盖**：寻找覆盖所有节点的最小路径集合，时间复杂度为O(N^3)。 - **最小点集覆盖**：寻找覆盖所有边的最小节点集合。 3. **Structure数据结构**： - **求某天是星期几**：通常涉及日期计算，可能需要用到历法规则。 - **左偏树**：一种自平衡二叉查找树，其合并操作复杂度为O(log N)。 - **树状数组**：也称为线段树，用于高效地处理区间查询和修改操作。 这些算法和数据结构是ACM/ICPC竞赛的核心内容，熟练掌握它们对于提高编程技能和解决实际问题非常有益。通过学习和实践这些代码，开发者能够更好地理解算法原理，提升解决问题的能力。