ACM竞赛必备：图论与算法代码集锦

"该资源是一份关于ACM竞赛编程的经典代码集合，涵盖了数论、图论中的匹配、生成树、网络流以及最短路径等多个重要算法。这些算法在解决复杂计算问题时非常关键，对于学习算法和准备ACM比赛的学生来说是必备参考资料。" 详细说明: 1. **数论**: - **阶乘最后非零位**：这部分可能包含计算阶乘后找到最后非零数字的方法，这对于理解大整数操作和模运算有帮助。 - **模线性方程(组)**：涉及解模线性方程或方程组，如扩展欧几里得算法，它在密码学和数论问题中常见。 - **素数表**：如何快速生成素数序列，可能包括埃拉托斯特尼筛法。 - **素数随机判定(miller_rabin)**：这是一种概率性测试，用于判断一个大数是否为素数。 - **质因数分解**：将一个数分解成素数的乘积，对于理解和处理大整数至关重要。 - **最大公约数欧拉函数**：求两个数的最大公约数并可能涉及到欧拉函数，这在数论中是基础操作。 2. **图论_匹配**: - **二分图最大匹配(hungary)**：匈牙利算法，用于寻找二分图中的最大匹配，有多种实现方式，如邻接表和邻接矩阵。 - **一般图匹配**：处理非二分图的匹配问题，可能包括 Dinic 或 Ford-Fulkerson 方法。 3. **图论_生成树**: - **最小生成树(kruskal/prim)**：Kruskal 和 Prim 算法分别通过边和顶点来构建最小生成树，这里包含了不同数据结构（如二叉堆）的实现。 4. **图论_网络流**: - **上下界最大流/最小流**：用于求解网络中的最大流量和最小费用流量问题，可以使用 Dinic 或 Ford-Fulkerson 模型的变种。 - **最大流**：找出网络中从源节点到汇点的最大流量，同样基于增广路径的算法。 - **最小费用最大流**：在保证最大流量的同时最小化总费用。 5. **图论_最短路径**: - **最短路径(bellman_ford/dijkstra)**：Bellman-Ford 算法可以处理负权边，Dijkstra 则不处理，这两种都是求单源最短路径的算法，有 BFS 和优先队列（如二叉堆、映射堆）的实现。 - **多源最短路径(floyd-warshall)**：Floyd-Warshall 算法用于计算所有顶点之间的最短路径，通常用邻接矩阵表示。 这份资料详尽地涵盖了ACM竞赛中常见的算法和数据结构，对于提升编程能力，特别是处理复杂问题的算法设计和实现技巧具有极高的学习价值。