上海交大ACM标准代码库：算法与数据结构精华

“上海交大ACM模板，ACMer值得一看” 上海交通大学的ACM模板代码库，由sqybi创建于2009年9月6日并进行了更新至9月9日，是一个针对算法竞赛（如ACM/ICPC）的标准化代码库。这个资源包含了多种基础和高级算法以及数据结构，旨在帮助参赛者快速解决问题，提高编程效率。 1. **算法与数据结构**： - **高精度整数**：处理超过标准类型所能表示的大整数运算。 - **高精度浮点数**：类似地，处理大数值的浮点运算。 - **分数运算**：支持分数的加减乘除等操作。 - **二叉堆**：用于优先队列和优化某些算法。 - **胜者树**：快速查询最小元素的动态集合。 - **数字树**：用于高效计算前缀和或范围查询。 - **线段树**：支持区间操作，如区间加、区间查询等。 - **并查集**：处理不相交集合的合并与查找。 - **快速排序**：经典的分治排序算法。 - **归并排序**：稳定排序，适合大量数据。 - **基数排序**：非比较型整数排序。 - **选择第K小元素**：在未排序的序列中找到第K小的元素。 - **KMP算法**：字符串匹配算法，避免冗余回溯。 - **后缀排序**：对字符串数组进行排序，以便进行模式匹配。 2. **图论与网络算法**： - **邻接表**：存储图的节点及其连接。 - **单源最短路径（Dijkstra+二叉堆）**：求解从单一节点到其他所有节点的最短路径。 - **单源最短路径（SPFA）**：Bellman-Ford算法的一种优化版本。 - **最小生成树（Kruskal）**：构造一个图的边集合，使得树的所有边权值之和最小。 - **最小有向生成树**：在有向图中寻找最小权值的生成树。 - **二分图的最大匹配**：寻找二分图中匹配数最大的边集。 - **二分图的最大费用完美匹配（n^4）**：寻找最大费用且完全匹配的边集。 - **二分图的最大费用完美匹配（n^3）**：更快的算法实现。 - **一般图的最大匹配**：扩展到非二分图的情况。 - **最大流（ Dinic 矩阵）**：在网络流问题中找出从源节点到汇点的最大流量。 - **最大流（ Dinic 链式前向增广）**：改进版最大流算法，利用链式结构加速。 - **最小成本最大流（矩阵形式）**：同时考虑流量和费用。 - **最小成本最大流（链式前向增广）**：在考虑费用的情况下优化网络流。 这些代码模板覆盖了ACM竞赛中常见的算法和数据结构，不仅适用于参赛者，也对学习算法和数据结构的程序员非常有价值。通过理解和运用这些模板，开发者可以提升解决复杂问题的能力，并提高代码的编写速度和质量。