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

"该资源是ACM编程竞赛中常用的经典代码集合，包含了丰富的算法实现，适合比赛使用和平时学习。代码涉及数论、图论（包括匹配、生成树和网络流）以及最短路径等核心算法，语言涵盖C和C++。" 详细说明： 1. **数论** - **阶乘最后非零位**：计算阶乘结果末尾连续零的数量，涉及到对质因数2和5的分析。 - **模线性方程(组)**：求解模意义下的线性同余方程或方程组，可能使用扩展欧几里得算法或中国剩余定理。 - **素数表**：生成一定范围内的素数序列，常用方法有埃拉托斯特尼筛法。 - **素数随机判定(miller_rabin)**：利用米勒-拉宾素性检验进行快速的素数判定，有一定的错误率。 - **质因数分解**：将一个整数拆分为质数的乘积。 - **最大公约数欧拉函数**：计算两个数的最大公约数，以及欧拉函数值φ(n)，用于数论问题。 2. **图论_匹配** - **二分图最大匹配**：应用匈牙利算法解决二分图中的最大匹配问题，提供了邻接表、邻接阵和正向表等多种实现形式。 - **一般图匹配**：解决非二分图的最大匹配问题，同样采用匈牙利算法或Kuhn-Munkres算法。 3. **图论_生成树** - **最小生成树**：包括Kruskal算法和Prim算法的不同实现，如邻接表、邻接阵、正向表配合二叉堆或映射堆等数据结构来寻找图的最小生成树。 4. **图论_网络流** - **上下界最大流/最小流**：处理带有上下界限制的网络流问题，通过增广路径和容量调整找到最大流量或最小费用流量。 - **最大流**：求解网络中的最大流量，如Ford-Fulkerson算法或 Dinic算法的实现。 - **最小费用最大流**：在保证最大流的前提下，寻求最小总费用的路径。 5. **图论_最短路径** - **最短路径**：包括Bellman-Ford算法、Dijkstra算法（BFS版本和优先队列版本）用于求解单源最短路径问题，适用于有负权边或无负权边的情况。 这些代码实现覆盖了ACM竞赛中常见的算法问题，对于参赛者和学习者来说是宝贵的参考资料。通过深入理解并实践这些代码，可以提升对算法的理解和编程能力。