ACM/ICPC算法集合：图论、网络流与数据结构

"该资源是一个ACM/ICPC竞赛相关的代码库，主要包含C++和C语言编写的算法源代码，涵盖了图论、网络流、数据结构等多个领域的问题解决方法。作者为jojer&Fandywang，来自吉林大学计算机科学与技术学院2005级。" 这篇摘要主要涉及了在ACM/ICPC竞赛中常见的算法和数据结构，下面将详细阐述这些知识点： 1. **Graph图论**： - **DAG的深度优先搜索标记**：在有向无环图(DAG)中使用深度优先搜索进行遍历并标记节点。 - **无向图找桥**：查找无向图中的桥，即那些删除后会使得图不连通的边。 - **无向图连通度(割)**：计算图的连通分量，寻找割点或割边以分割图。 - **最大团问题**：在无向图中找到最大的完全子图，可以用动态规划和DFS解决。 - **欧拉路径**：寻找起点到终点经过每条边一次且仅一次的路径。 - **DIJKSTRA**：Dijkstra算法，用于找出图中所有顶点到指定顶点的最短路径，有两种实现方式：数组实现和优先队列优化。 - **BELLMAN-FORD**：Bellman-Ford算法，可以处理负权边，找到所有顶点到指定顶点的最短路径。 - **SPFA**：Shortest Path Faster Algorithm，一种基于队列的优化Dijkstra算法，用于求解单源最短路径。 - **第K短路**：除了最短路径外，还可以找到第K短的路径，可以使用Dijkstra或A*算法改进。 2. **Network网络流**： - **二分图匹配**：匈牙利算法，包括DFS和BFS实现，以及Hopcroft-Carp算法，用于寻找二分图的最大匹配。 - **KUHN-MUNKRAS算法**：求解二分图最佳匹配，效率为O(M*M*N)。 - **最小割**：寻找无向图中最小的割，可以用于判断是否存在匹配。 - **最大流**：包括Dinic算法和HLPP算法，用于在有向图中寻找从源点到汇点的最大流量。 - **最小费用流**：同时考虑边的权重，找到最大流量的同时最小化总费用。 3. **Structure数据结构**： - **求某天是星期几**：可能涉及日期计算和星期的转换。 - **左偏树**：一种特殊的二叉堆，合并操作的时间复杂度为O(LOGN)。 - **树状数组**：用于高效地进行区间查询和修改操作的数据结构。 - **二维树状数组**：扩展树状数组以支持二维区间操作。 - **TRIE树**：前缀树，用于高效地存储和查询字符串集合。 - **后缀数组**：用于处理字符串后缀的排序和查找，有O(N*LOGN)和O(N)两种构建方法。 - **RMQ**：Range Minimum Query，用于查找区间内的最小值，离线算法可以在预处理后常数时间内查询。 这个代码库提供了丰富的ACM/ICPC竞赛所需的基础和高级算法，对于学习算法和参加此类竞赛的人来说极具价值。