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

"吉林大学ACM/ICPC代码库，包含吉林大学计算机科学与技术学院2005级2007-2008年的ACM竞赛经典代码，由ACMGroup1成员维护和更新。该代码库涵盖算法模板和数据结构，包括图论、网络流和数据结构等多个方面，旨在帮助学习和解决竞赛中的算法问题。" 在这个代码库中，重点介绍了以下几个算法和数据结构的知识点： 1. **Graph图论**： - **DAG的深度优先搜索（DFS）标记**：用于遍历有向无环图（DAG），标记节点的访问状态。 - **无向图找桥**：在无向图中查找桥（关键边），这些边移除后会使得图分成两个或更多不连通部分。 - **无向图连通度（割）**：计算图的连通分量数量，判断是否为强连通图。 - **最大团问题**：寻找图中最大的完全子图，可以使用动态规划（DP）和深度优先搜索（DFS）结合的方法。 - **欧拉路径**：找到一个起点和终点相同的路径，经过图中所有边且仅经过一次。 - **Dijkstra算法**：求解单源最短路径，这里提供了两种实现：数组实现（时间复杂度O(N^2)）和优化后的版本（时间复杂度O(E*logE)）。 - **Bellman-Ford算法**：适用于存在负权边的情况，求解单源最短路径，时间复杂度为O(VE)。 - **SPFA（Shortest Path Faster Algorithm）**：一种基于队列的优化版Dijkstra算法，用于求解单源最短路径。 - **第K短路**：找到起点到其他节点的第K条最短路径，这里分别用Dijkstra和A*算法实现。 - **Prim算法**：求最小生成树，这里用于无向图，时间复杂度为O(V^2)。 - **次小生成树**：寻找第二小的生成树，通常使用Kruskal算法的一个变种。 - **最小生成森林问题**：处理包含K棵树的最小生成树，可以使用Disjoint Set实现，时间复杂度为O(M*logM)。 - **有向图最小树形图**：在有向图中找到最小树形图，即找到一棵最小的树形子图，其中每个节点的出度最多为1。 - **Tarjan强连通分量**：检测并找到有向图中的强连通分量。 - **弦图判断**：识别一个图是否为弦图，并找到完美消除顺序。 - **稳定婚姻问题**：使用Gale-Shapley算法，解决稳定性问题，时间复杂度为O(N^2)。 - **拓扑排序**：对于有向无环图进行排序，使每条有向边指向的节点都位于其起点的后面。 2. **Network网络流**： - **二分图匹配**：使用匈牙利算法通过DFS和BFS实现，寻找二分图中的最大匹配。 - **Hopcroft-Carp算法**：另一种二分图匹配的算法。 - **Kuhn-Munkres算法（KM算法）**：求解二分图的最佳匹配，效率较高，时间复杂度为O(M*M*N)。 - **无向图最小割**：寻找图中最小割，将图分为两个部分。 - **有上下界最小（最大）流**：在网络流中，考虑流量的上下界限制。 - **Dinic算法**：求解最大流，时间复杂度为O(V^2*E)。 - **HLPP算法**：Halperin-Lovász-Papadimitriou-Papadimitriou算法，用于求解最大流，时间复杂度为O(V^3)。 - **最小费用流**：在满足流约束的同时最小化总费用，这里提供了两种实现，时间复杂度分别为O(V*E*F)和O(V^2*F)。 - **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集（点连通度）**：涉及最小割在不同条件下的优化问题。 - **最小路径覆盖**：找到覆盖图中所有边的最小路径集合。 - **最小点集覆盖**：寻找覆盖图中所有边的最小顶点集合。 3. **Structure数据结构**： - **求某天是星期几**：可能涉及日期处理和模运算，用于确定给定日期是星期几。 这个代码库提供了丰富的ACM竞赛常用算法和数据结构的实现，对于参赛者和算法学习者来说是一份宝贵的参考资料。