ACM图论与网络流算法总结

"这份资源是吉林大学ACM/ICPC代码库的一部分，包含了大量用于解决算法竞赛问题的经典代码。涵盖图论、网络流和数据结构等多个领域的知识点，旨在帮助参赛者提升编程技能和解决问题的能力。" 在图论部分，文档详细介绍了各种经典算法： 1. **DAG的深度优先搜索标记**：在有向无环图(DAG)中进行DFS，标记节点性质。 2. **无向图找桥**：识别无向图中的桥（关键边），这些边移除后会使得图分块。 3. **无向图连通度**：计算图的连通分量，了解图的割点和割边。 4. **最大团问题**：利用动态规划和DFS寻找无向图中最大的完全子图。 5. **欧拉路径**：找到从一个顶点出发遍历所有边并返回原点的路径，O(E)时间复杂度。 6. **DIJKSTRA算法**：两种实现方式，数组实现O(N^2)和优化后的O(E*LOGE)，用于寻找单源最短路径。 7. **BELLMAN-FORD算法**：寻找单源最短路径，可以处理负权边，O(VE)时间复杂度。 8. **SPFA算法**：一种比DIJKSTRA更快的最短路径算法，但可能不总是最优。 9. **第K短路**：寻找除了最短路径外的第K短路径，通过DIJKSTRA或A*算法实现。 10. **PRIM算法**：最小生成树的构造，O(V^2)时间复杂度。 11. **次小生成树**：寻找次小生成树，通常使用Kruskal或Prim的变种。 12. **最小生成森林问题**：处理多棵生成树，如Kruskal算法，O(MLOGM)时间复杂度。 13. **有向图最小树形图**：在有向图中寻找最小树形图。 14. **TARJAN强连通分量**：找出有向图中的强连通分量。 15. **弦图判断**：识别弦图及其完美消除点排列。 16. **稳定婚姻问题**：用O(N^2)的时间解决Stable Marriage Problem。 17. **拓扑排序**：对有向无环图进行排序，确保无前驱的节点排在前面。 18. **无向图连通分支**：使用DFS或BFS遍历连通分支。 19. **有向图强连通分支**：使用DFS遍历强连通分支，O(N^2)时间复杂度。 20. **有向图最小点基**：在邻接阵上求解最小点基，O(N^2)时间复杂度。 21. **FLOYD求最小环**：寻找图中最小环的算法。 22. **2-SAT问题**：解决布尔逻辑中2-SAT问题。 在网络流部分，文档涵盖了多种算法： 1. **二分图匹配**：包括匈牙利算法的DFS和BFS实现，以及HOPCROFT-CARP算法。 2. **二分图最佳匹配**：通过KUHN-MUNKRAS算法在二分图中寻找最佳匹配。 3. **无向图最小割**：寻找最小割以分割图，O(N^3)时间复杂度。 4. **有上下界的最小(最大)流**：处理带容量限制的网络流问题。 5. **DINIC最大流**：Dinic算法用于求解最大流，时间复杂度O(V^2*E)。 6. **HLPP最大流**：采用HLPP算法，时间复杂度O(V^3)。 7. **最小费用流**：同时考虑费用和流量，有O(V*E*F)和O(V^2*F)两种实现。 8. **最佳边割集**、**最佳点割集**、**最小边割集**和**最小点割集（点连通度）**：涉及割点和割边的选择。 9. **最小路径覆盖**：寻找最小的路径集合以覆盖所有顶点，O(N^3)时间复杂度。 10. **最小点集覆盖**：寻找最小的顶点子集来覆盖所有边。 在数据结构部分，涵盖了多种实用数据结构和算法： 1. **求某天是星期几**：根据日期计算对应的星期。 2. **左偏树**：合并复杂度为O(LOG N)的特殊二叉树结构。 3. **树状数组**：用于高效地执行区间修改和查询操作。 4. **二维树状数组**：扩展树状数组以处理二维区间问题。 5. **TRIE树**：用于存储字符串，分为K叉和左儿子右兄弟两种实现。 6. **后缀数组**：构建和查询字符串后缀，有O(N * LOG N)和O(N)两种构造方法。 7. **RMQ（Range Minimum/Maximum Query）**：离线算法求解区间最值，包括O(N*LOGN)+O(1)版本。 8. **LCA（Lowest Common Ancestor）**：求解树中两个节点的最近公共祖先，离线算法O(E)+O(1)。 9. **带权值的并查集**：支持加权联合操作的并查集结构。 10. **快速排序**：高效的排序算法。 11. **2台机器工作调度**：优化两台机器的工作安排问题。 12. **大数比较和运算**：处理大整数的比较和基本运算。 13. **最长公共递增子序列**：寻找序列中LIS（Longest Increasing Subsequence）。 14. **0-1分数规划**：处理线性规划问题，允许变量取0或1。 15. **最长有序子序列**：寻找递增、递减或非递增/递减子序列。 16. **模线性方程**：求解模线性方程A * X = B (% N)。 17. **模线性方程组**：处理模线性方程组。 18. **筛素数**：高效地找出[1..N]范围内的所有素数。 19. **随机素数测试**：基于伪素数原理的素数检验方法。 20. **组合数学相关**：包括POLYA计数、组合数C(N, R)等。 21. **最大1矩阵**：寻找具有最大1数量的子矩阵。 22. **约瑟夫环问题**：通过数学方法和数组模拟解决环形链表问题。 23. **取石子游戏1**：分析和解决石头游戏策略。 24. **集合划分问题**：将元素集合划分为满足特定条件的子集。 这个资源提供了丰富的ACM竞赛常用代码，对于准备算法竞赛、提高编程技能和理解复杂算法有极大帮助。