ACM竞赛必备：代码集锦

"该资源是一份ACM竞赛中常用的经典代码集合，适合参赛者和学习者参考使用。包含了数论、图论相关的算法实现，如模线性方程、最大公约数、最大匹配、最小生成树、网络流以及最短路径等核心问题的解决方案。" 在ACM编程竞赛中，掌握高效算法是关键。这份代码集主要涵盖了以下几个方面： 1. **数论**： - **阶乘最后非零位**：计算阶乘结果最后非零位的算法，这涉及到大整数操作和模运算。 - **模线性方程(组)**：解决同余方程组，通常使用扩展欧几里得算法或中国剩余定理。 - **素数表**：快速生成一定范围内的素数列表，可以使用Sieve of Eratosthenes算法。 - **素数随机判定（miller_rabin）**：概率性素数判定方法，具有较高的正确率。 - **质因数分解**：将一个合数拆分成质因数的乘积，常用方法有Pollard's rho或Williams' p-1。 - **最大公约数欧拉函数**：计算两个数的最大公约数并利用欧拉函数进行操作。 2. **图论_匹配**： - **二分图最大匹配**：包括Kuhn-Munkres算法和匈牙利算法，用于找到图中二分图的最大匹配。 - **一般图匹配**：处理非二分图的匹配问题，可能需要用到Edmonds-Karp算法或 Dinic's algorithm。 3. **图论_生成树**： - **最小生成树**：包括Kruskal和Prim算法，用于找到连接所有节点的最小权值边集合。这里还提到了优先队列（如二叉堆）的实现。 4. **图论_网络流**： - **最大流**：解决网络中的最大传输能力问题，如Ford-Fulkerson算法和Edmonds-Karp算法。 - **最小费用最大流**：在保证最大流的同时，寻找最小总费用的路径，通常结合 Dinic's algorithm 或 Bellman-Ford算法。 5. **图论_最短路径**： - **最短路径**：包括Bellman-Ford算法（可处理负权边）和Dijkstra算法（不处理负权边），其中Dijkstra算法有基于优先队列的不同实现。 这些算法是ACM竞赛和图论学习中的基础，理解并熟练运用它们对于提升解题能力和优化代码效率至关重要。通过学习和参考这份代码集，参赛者和学习者可以更好地理解和实践这些经典算法。