上海交大ACM算法模板：数据结构与图论精华

“上海交大ACM模板（by sqybi）”是一份由上海交通大学的sqybi编写的算法和数据结构代码库，主要用于ACM（国际大学生程序设计竞赛）和ICPC（国际大学生程序设计竞赛）的训练。这份模板更新于2009年9月9日，包含了五个主要部分：算法与数据结构、图论与网络算法、数论、代数算法以及计算几何。 在“算法与数据结构”部分，模板提供了以下内容： 1. 高精度整数：用于处理超过标准整型范围的大整数运算。 2. 高精度浮点数：处理大数值或高精度浮点计算。 3. 分数类：用于分数运算，便于处理有理数问题。 4. 二叉堆：实现堆排序或优先队列的高效数据结构。 5. 赢家树：一种用于快速查找最大值的数据结构。 6. 数位树：常用于统计数字数组中特定数字出现的次数。 7. 区间树（Segment Tree）：用于区间查询和修改操作。 8. 并查集：处理集合的合并与查询，常用于判断元素是否属于同一集合。 9. 快速排序：一种高效的排序算法，采用分治策略。 10. 归并排序：稳定的排序算法，通过归并操作保证排序稳定性。 11. 基数排序：按位进行排序，适合于非负整数的排序。 12. 寻找第K小的元素：在数组中找到第K小的元素，适用于快速查找特定位置的元素。 13. KMP模式匹配：提高字符串匹配效率，避免冗余回溯。 14. 后缀排序：对字符串进行排序，便于进行后缀数组的构建和LCP数组的计算。 在“图论与网络算法”部分，该模板涵盖了： 1. 邻接表：表示图的一种数据结构，节省空间。 2. 单源最短路径（Dijkstra + Binary Heap）：求解起点到图中所有其他顶点的最短路径。 3. Bellman-Ford算法（SPFA）：求解单源最短路径，能处理负权边。 4. 最小生成树（Kruskal）：用Prim或Kruskal算法找到图的最小生成树。 5. 最小有向生成树：求解最小有向生成树的问题。 6. 二分图的最大匹配：寻找二分图中最大数量的互不冲突的边。 7. 二分图的最大费用完美匹配：考虑边的权重，寻找最大总权重的完美匹配。 8. 一般图的最大匹配：扩展到非二分图的最大匹配问题。 9. Dinic算法在矩阵形式下的最大流：解决网络流问题，寻找从源点到汇点的最大流量。 10. Dinic算法在链式前向星形式下的最大流：同样用于求解最大流问题，但数据结构更紧凑。 11. 最小费用最大流（在矩阵中）：考虑费用和流量，寻找最大流量且总费用最小的方案。 12. 最小费用最大流（在链式前向星中）：同样求解最小费用最大流问题。 这份模板是ACM/ICPC竞赛选手的重要参考资料，包含了许多基础和高级的算法实现，能够帮助参赛者快速解决各种编程竞赛中的问题。对于学习算法和数据结构的学生，也是极好的学习资源。