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

"上海交大ACM-ICPC模板是由上海交通大学计算机科学与工程系的Hao Yuan在2003年10月23日编写的，它包含了一个标准的代码库，专为参加ACM国际大学生程序设计竞赛（ACM-ICPC）的团队准备。这个模板涵盖了算法和数据结构等多个方面，旨在帮助参赛者快速解决竞赛中的问题。" 该模板详细介绍了多种关键算法和数据结构，包括： 1. 高精度计算：在C语言和C++中实现高精度运算，这对于处理大整数和浮点数的精确计算至关重要。 2. 分数类：定义一个分数类，用于方便地进行分数运算，支持加、减、乘、除等操作。 3. 二叉堆：二叉堆是一种特殊的数据结构，常用于优先队列和最大/最小元素查找。 4. 赢家树：赢家树（也称为最小堆）是解决动态区间最值问题的有效方法。 5. 数位树：数位树（也称作数字根树）用于高效地处理基于数位的操作，如求和或查找特定模式。 6. 区间树（Segment Tree）：区间树可以在线性时间内完成区间查询和更新操作，适用于处理区间统计问题。 7. IOI'2001中的区间树：这是对原区间树的一种特定应用或变体，可能涉及到更复杂的问题场景。 8. 并查集：并查集用于处理集合的合并与查找操作，常用于判断元素间是否存在连接关系。 9. 快速排序：快速排序是一种高效的排序算法，平均时间复杂度为O(n log n)。 10. 归并排序：归并排序也是一种稳定的排序算法，适合大规模数据的排序。 11. 基数排序：基数排序是按数字的每一位进行排序，特别适用于非负整数的排序。 12. 寻找第k小元素：在未排序的数组中寻找第k小元素，可以使用快速选择算法或其他方法。 13. KMP算法：KMP算法是一种高效的字符串匹配算法，避免了多余的回溯。 14. 后缀排序：后缀排序可用于查找字符串的所有后缀，为字符串搜索和模式匹配提供便利。 在图论和网络算法部分，模板涵盖了： 1. 单源最短路径：包括Dijkstra算法（配合二叉堆优化）和Bellman-Ford算法（处理负权边）。 2. 最小生成树：Kruskal算法用于构建没有环的最小生成树。 3. 最小有向生成树：处理有向图的最小生成树问题。 4. 二分图的最大匹配：找到二分图中最大的匹配数。 5. 二分图的最大完美匹配：在二分图中寻找每个节点都能匹配的完美匹配。 6. 一般图的最大匹配：解决非二分图的最大匹配问题。 7. 最大流：Ford-Fulkerson算法的矩阵版本和链式版本，用于计算网络中的最大流。 8. 最小费用最大流：在考虑费用的情况下求解最大流问题。 9. 辨识圈图：识别具有特定性质的圈图，如无圈图等。 这些算法和数据结构的实现是ACM-ICPC竞赛中的核心竞争力，学习和掌握它们将大大提高参赛队伍解决问题的能力。