ACM竞赛必备：经典图论与数论代码集锦

"这是一份全面的ACM竞赛编程代码集合，涵盖了数论、图论中的关键算法，包括匹配、生成树、网络流和最短路径等核心问题。适合对算法有深入研究或准备参加ACM竞赛的学习者参考。" 在ACM经典代码大全中，我们可以看到以下几个重要的知识领域： 1. **数论**： - 阶乘最后非零位：涉及到大整数计算和模运算，理解数的性质以及如何快速计算阶乘的尾部零。 - 模线性方程(组)：利用中国剩余定理或扩展欧几里得算法解决模线性问题。 - 素数表与素数随机判定（miller_rabin）：高效生成素数表，以及使用miller_rabin算法进行素数的快速判断。 - 质因数分解：将一个数拆解成质数的乘积，常用的方法有Pollard's rho、Pollard's p-1等。 - 最大公约数与欧拉函数：计算两个数的最大公约数（GCD），以及欧拉函数φ(n)，用于计算小于等于n且与n互质的数的数量。 2. **图论_匹配**： - 二分图最大匹配：匈牙利算法（Kuhn-Munkres算法）用于寻找二分图的最大匹配，包括多种实现方式，如邻接表和邻接矩阵形式。 - 一般图匹配：处理非二分图的匹配问题，同样使用匈牙利算法或其他算法。 3. **图论_生成树**： - 最小生成树：包括Kruskal算法和Prim算法，分别基于边的权值和顶点的权值构建最小生成树，有邻接表、正向表和邻接矩阵的不同实现。 4. **图论_网络流**： - 上下界最大流/最小流：用于求解网络中的最大流量或最小费用流量，通常使用Ford-Fulkerson或 Dinic算法。 - 最大流：同上，但不考虑上下界限制。 - 最小费用最大流：在保证最大流的同时最小化总费用，可以结合增广路径和成本更新策略来实现。 5. **图论_最短路径**： - 单源最短路径：包括Bellman-Ford算法（处理负权边）、Dijkstra算法（不处理负权边）以及它们的优化版本，如使用优先队列（binary_heap或mapped_heap）加速查找。 这些算法是ACM竞赛中常见的问题，掌握它们对于解决复杂问题和提高编程效率至关重要。每一种算法都有其特定的应用场景和优化策略，理解和熟练运用这些知识是提升编程技能的关键。