ACM代码集：图论与网络流算法详解

"这份资源是吉林大学ACM/ICPC代码库的一部分，包含了大量用于解决算法竞赛的经典代码，涵盖图论、网络流、数据结构等多个领域。这些代码由2005级计算机科学与技术学院的学生在2007-2008年间编写和修订。" 在这份代码库中，你可以找到以下关键知识点： **图论**： 1. **DAG深度优先搜索**：用于遍历有向无环图（DAG），标记节点状态。 2. **寻找无向图中的桥**：桥是指如果去掉会使得图不连通的边。 3. **无向图连通度**：计算无向图的最大连通分量数量。 4. **最大团问题**：寻找图中最大的完全子图，可以用动态规划和DFS解决。 5. **欧拉路径**：在欧拉图中找到一条通过所有边且只通过一次的路径。 6. **Dijkstra算法**：用于求解单源最短路径，有两种实现方式，分别是基于数组和基于优先队列（如 Fibonacci heap）。 7. **Bellman-Ford算法**：处理带有负权重边的单源最短路径问题。 8. **SPFA算法**：一种比Dijkstra更简单但可能较慢的单源最短路径算法。 9. **第K短路径**：找到除了最短路径外的第K短路径，可以使用Dijkstra或A*算法扩展。 10. **Prim算法**：求最小生成树，适用于无向图。 11. **Kruskal算法**：另一种求最小生成树的方法，适用于无向图。 12. **最小生成森林**：处理多棵最小生成树的问题。 13. **有向图最小树形图**：寻找有向图的最小树形图，通常与Steiner树问题相关。 14. **Tarjan算法**：用于检测和计算图的强连通分量。 15. **弦图的Perfect Elimination点排列**：弦图的性质和处理方法。 16. **稳定婚姻问题**：使用Gale-Shapley算法求解稳定匹配。 17. **拓扑排序**：对于有向无环图，按顺序排列节点，使得每条边指向的节点都排在前面。 18. **无向图连通分支**：使用DFS或BFS查找无向图的连通分支。 19. **有向图强连通分支**：同样使用DFS或BFS找到有向图的强连通分量。 20. **有向图最小点基**：在邻接矩阵表示的有向图中找到最小点基。 21. **Floyd-Warshall算法**：求解所有顶点对间的最短路径。 22. **2-SAT问题**：解决布尔逻辑中的2变量满足问题。 **网络流**： 23. **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及Hopcroft-Carp算法。 24. **Kuhn-Munkres算法**：求解二分图的最佳匹配。 25. **无向图最小割**：在无向图中找到最小割，分割图成两部分。 26. **有上下界约束的最小（最大）流**：在网络流中处理带上下界限制的流量。 27. **Dinic算法**：求解最大流，时间复杂度为O(V^2 * E)。 28. ** HLPP算法**：求解最大流，时间复杂度为O(V^3)。 29. **最小费用流**：同时考虑流量和费用，有不同时间复杂度的实现。 30. **最佳边割集** 和 **最佳点割集**：寻找具有最小费用的割。 31. **最小边割集** 和 **最小点割集（点连通度）**：在图中寻找最小的割集。 32. **最小路径覆盖**：找到覆盖所有边的最小路径集合。 33. **最小点集覆盖**：找到覆盖所有边的最小顶点集合。 **数据结构**： 34. **求某天是星期几**：根据日期计算星期。 35. **左偏树**：一种自平衡二叉堆，用于高效合并操作。 36. **树状数组**（也称为 BIT，Fenwick Tree）：快速查询和更新区间加法。 37. **二维树状数组**：扩展树状数组到二维空间，用于处理二维区间问题。 38. **Trie树**（前缀树）：用于高效存储和查询字符串前缀。 39. **后缀数组**：构建和利用后缀数组进行字符串处理，有线性时间和线性对数时间的构建方法。 40. **RMQ（Range Minimum/Maximum Query）**：区间最小/最大值查询，包括离线算法和ST算法。 41. **LCA（Lowest Common Ancestor）最近公共祖先**：在线下求解LCA问题。 42. **带权值的并查集**：用于处理带有权重的联合问题。 43. **快速排序**：高效的排序算法，平均时间复杂度为O(N log N)。 44. **两台机器的工作调度**：优化分配任务给两台机器的问题。 45. **大数运算**：包括高效和普通的大数计算方法。 46. **最长公共递增子序列**：寻找两个序列中的最长递增子序列。 47. **0-1分数规划**：处理0-1变量的线性规划问题。 48. **最长有序子序列**：找出一个序列中最长的递增或递减子序列。 49. **模线性方程**：解决模意义下的线性方程和方程组。 50. **筛素数**：高效地找出一定范围内的所有素数。 51. **随机素数测试**：基于伪素数原理的素数检测方法。 52. **组合数学**：包括Polya计数、组合数C(N, R)等。 53. **最大1矩阵**：寻找矩阵中的最大1子矩阵。 54. **约瑟夫环问题**：数学方法和数组模拟解决循环报数问题。 55. **取石子游戏**：一种两人博弈问题。 56. **集合划分问题**：将集合分成多个子集，每个子集互斥。 以上这些知识点涵盖了ACM/ICPC竞赛中常见的算法和数据结构，对于提升编程能力和解决复杂问题具有极高的价值。