吉林大学ACM竞赛代码库与算法总结

"ACM吉林大学模板" 这篇资源主要涵盖了ACM竞赛中常见的算法和数据结构，特别是针对图论、网络流以及数据结构的问题。以下是这些领域的详细知识点： 1. **Graph图论** - **DAG的深度优先搜索标记**：在有向无环图（DAG）中，深度优先搜索（DFS）常用于标记节点，如判断有无环，计算拓扑排序等。 - **无向图找桥**：寻找图中的桥（关键边），即删除后会导致图中至少一个连通分量数量增加的边。 - **无向图连通度**：确定图的连通分量，理解图的分块结构。 - **最大团问题**：寻找图中最大的完全子图，可以使用动态规划（DP）结合DFS来解决。 - **欧拉路径**：找到一个图中经过所有边恰好一次的路径，O(E)表示线性时间复杂度。 - **DIJKSTRA算法**：用于求解单源最短路径问题，有两种实现方式：数组实现O(N^2)和优化后的O(E*LOGE)。 - **BELLMAN-FORD算法**：处理带有负权边的单源最短路径问题，时间复杂度为O(VE)。 - **SPFA算法**：Shortest Path Faster Algorithm，一种求解单源最短路径的启发式方法，效率优于Bellman-Ford。 - **第K短路**：除了最短路径外，还需要寻找第K短的路径，可以利用Dijkstra或A*算法进行改进。 - **PRIM算法**：用于求解最小生成树（MST），时间复杂度为O(V^2)。 - **次小生成树**：找到第二小的生成树，通常使用Kruskal或Edmonds-Karp算法，这里给出的时间复杂度为O(V^2)。 - **最小生成森林问题**：解决多棵树的最小生成树问题，常见算法有Prim's和Kruskal's，这里的时间复杂度为O(MLOGM)。 - **有向图最小树形图**（最小点基）：找到一个树形子图，使得所有顶点都有入边，常用邻接矩阵实现，时间复杂度为O(N^2)。 - **TARJAN强连通分量**：检测图中各个强连通分量，用于分析有向图的结构。 - **弦图判断及PERFECT ELIMINATION点排列**：弦图是指图中每一条边都是某圈的弦，PERFECT ELIMINATION是指点排列的一种特性。 - **稳定婚姻问题**：Gale-Shapley算法，解决分配问题，如稳定婚姻配对，时间复杂度为O(N^2)。 - **拓扑排序**：对DAG进行排序，使得对于每一条有向边 (u, v)，u的排序位置总在v之前。 2. **Network网络流** - **二分图匹配**：寻找最大匹配，包括DFS和BFS实现的匈牙利算法，以及Hopcroft-Carp算法。 - **KUHN-MUNKRAS算法**：高效解决二分图最佳匹配问题，时间复杂度为O(M*M*N)。 - **无向图最小割**：寻找分割图中两个部分的最小边集合，通常用Ford-Fulkerson方法或Edmonds-Karp算法。 - **有上下界的最小(最大)流**：在网络流中考虑边的流量限制和容量，用于优化问题。 - **DINIC算法**：最大流算法，具有O(V^2*E)的时间复杂度。 - **HLPP最大流**：Hierarchical Label Propagation Pushing算法，时间复杂度为O(V^3)。 - **最小费用流**：同时考虑边的费用和容量，求解最小总费用的最大流，两种时间复杂度分别为O(V*E*F)和O(V^2*F)。 - **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集**：涉及网络流的割集问题，用于优化网络性能。 - **最小路径覆盖**：寻找覆盖所有顶点的最小路径集合，时间复杂度为O(N^3)。 - **最小点集覆盖**：寻找覆盖所有边的最小顶点集合，是经典的组合优化问题。 3. **Structure数据结构** - **求某天是星期几**：根据日期计算星期，涉及到日期处理和模运算。 - **左偏树**：一种自平衡二叉查找树，其合并操作具有O(LOGN)的时间复杂度。 - **树状数组**（也称为二进制索引树）：用于高效地处理区间查询和修改操作，常见于在线算法。 这些知识点是ACM竞赛中的核心内容，掌握它们对于解决实际编程问题和算法竞赛至关重要。