上海交大袁豪版ACM/ICPC标准代码库

"ACM/ICPC参赛者必备的C++模版库，由上海交大袁豪编撰，包含了ACM/ICPC竞赛中常见的各种算法和数据结构，如高精度计算、堆、树、排序、图论与网络算法等。" 这篇文档是一个专门针对ACM/ICPC（国际大学生程序设计竞赛）参赛者的C++代码模版库，由上海交通大学计算机科学与工程系的袁豪编写。这份资源在国内外ACM/ICPC圈子内有着广泛的传播和应用，是参赛者准备比赛的重要参考资料。 1. **算法和数据结构**： - **高精度计算**：提供了C和C++两种语言实现高精度计算的方法，这对于处理大整数运算至关重要。 - **分数类(FractionClass)**：实现了分数的存储和运算，支持基本的加减乘除操作。 - **二叉堆(BinaryHeap)**：用于优先队列，实现快速插入、删除和查找最小元素。 - **胜者树(WinnerTree)**和**数字树(DigitalTree)**：通常用于高效地进行区间查询和修改操作。 - **线段树(SegmentTree)**：支持区间查询和更新，常见于解决动态区间问题。 - **并查集(Union-FindSet)**：处理不相交集合的连接和查询问题。 - **快速排序(QuickSort)**和**归并排序(MergeSort)**：两种经典的排序算法，各有优缺点，适用于不同场景。 - **基数排序(RadixSort)**：适用于非负整数排序，效率高且稳定。 - **选择第K小元素(SelectKthSmallestElement)**：在数组中快速找到第K小的元素。 - **KMP算法**：一种高效的字符串匹配算法，避免了冗余的回溯。 - **后缀排序(SuffixSort)**：对字符串进行排序，常用于模式匹配和最长公共前后缀等问题。 2. **图论和网络算法**： - **单源最短路径(SSSP)**：包括Dijkstra算法（配以二叉堆优化）和Bellman-Ford算法（配以队列）。 - **最小生成树(MST)**：涵盖了Kruskal算法。 - **最小有向生成树**：在有向图中寻找权值最小的生成树。 - **二分图的最大匹配(MaximumMatchingonBipartiteGraph)**：寻找二分图中的最大匹配数。 - **二分图的最大费用完美匹配(MaximumCostPerfectMatchingonBipartiteGraph)**：考虑边的费用，求解最大费用完美匹配。 - **一般图的最大匹配(MaximumMatchingonGeneralGraph)**：在非二分图中寻找最大匹配。 - **最大流(MaximumFlow)**：包含Ford-Fulkson算法的矩阵形式和链式前向星形式。 - **最小费用最大流(MinimumCostMaximumFlow)**：在考虑费用的情况下求解最大流问题。 - **识别圈状图(RecognizingChordalGraph)**：检测一个图是否为圈状图，即是否存在一个边集使得图成为简单环形。 这份模版库覆盖了算法竞赛中涉及的大部分核心算法和数据结构，对于提升参赛者的编程能力和解决问题的能力具有极大的帮助。通过学习和实践这些模版，参赛者可以迅速应对各种复杂的问题，并在比赛中取得更好的成绩。