浙江大学ACM竞赛模板：几何、组合、图论算法详解

"浙江大学ACM模板.doc" 是一份关于算法竞赛和编程的文档，主要涵盖了计算机科学中的多个重要领域，包括几何、组合数学、数据结构、数论、数值计算、图论以及网络流等。这份模板是浙江大学ICPC团队日常使用的代码库，由WishingBone在2002年创建，并在2004年由Riveria更新。 1. 几何（Geometry）： - 注意：这部分可能包含了处理几何问题时需要注意的事项。 - 几何公式：文档中可能列举了各种几何计算所需的公式。 - 多边形：多边形的定义、性质及操作，如判断是否共面、计算周长和面积。 - 多边形切割：如何将一个多边形分割成更小的部分。 - 浮点函数：处理浮点数运算，可能包括精度控制和近似计算。 - 面积：计算平面图形的面积。 - 球面：涉及球体的计算，如球面坐标和球面面积。 - 三角形：三角形的性质和计算，如内角和、外接圆半径等。 - 三维几何：涉及到三维空间中的几何问题，如点、线、面的关系。 - 凸包：计算点集的最小外接凸多边形。 - 网格：二维或三维网格的相关算法。 - 圆：圆的性质和计算，如圆心、半径、弦长等。 - 整数函数：可能与整数几何相关的函数。 2. 组合（Combinatorics）： - 组合公式：包括组合数的计算公式。 - 排列组合生成：生成所有可能的排列和组合。 - Gray码生成：生成无权循环码，用于避免相邻二进制编码差异太大。 - 置换（Polya）：可能涉及到排列的计数和变换。 - 字典序全排列和组合：按字典序生成排列和组合。 3. 结构（Structures）： - 并查集：用于处理集合合并和查询的高效数据结构。 - 堆：实现优先队列，包括大顶堆和小顶堆。 - 线段树：用于区间查询和修改的数据结构。 - 子段和：快速计算一段连续元素的和。 - 子阵和：类似线段树，但处理矩阵的子区域和。 4. 数论（Number Theory）： - 阶乘最后非0位：计算阶乘末尾非零数字的个数。 - 模线性方程组：求解同余方程组的方法。 - 素数：素数检测和素数相关的算法。 - 欧拉函数：计算小于或等于给定数n的正整数中与n互质的数的数量。 5. 数值计算（Numerical Computation）： - 定积分计算（Romberg方法）：数值积分的一种方法。 - 多项式求根（牛顿法）：求解多项式方程根的迭代方法。 - 周期性方程（追赶法）：解决周期性方程的算法。 6. 图论—NP搜索（Graph Theory—NP Search）： - 最大团：寻找图中最大完全子图的问题。 - 更快的最大团算法：针对规模较小的图。 7. 图论—连通性（Graph Theory—Connectivity）： - 无向图的关键点和关键边：基于深度优先搜索的判断和计算。 - 无向图的块和连通分支：图的块分解和连通性分析。 - 有向图的强连通分支：确定有向图中强连通分量。 - 有向图的最小点基：可能与图的拓扑排序相关。 8. 图论—匹配（Graph Theory—Matching）： - 二分图最大匹配：匈牙利算法的应用，包括不同表示形式。 - 一般图匹配：在非二分图中寻找最大匹配。 9. 图论—网络流（Graph Theory—Network Flow）： - 最大流：求解网络中最大流量的问题。 - 上下界最大流和最小流：处理带容量限制和下界的情况。 - 无流量最大流：处理某些节点没有出度或入度的情况。 - 最小费用最大流：考虑流成本的最优化问题。 10. 图论—应用（Graph Theory—Applications）： - 欧拉回路：判断是否存在通过每个边恰好一次的路径。 - 树的前序表转化：将树的前序遍历结果转化为其他形式。 - 树的优化算法：可能包括树的压缩、路径查找等。 - 拓扑排序：对有向无环图进行线性排序。 - 最佳边割集和点割集：找到分割图的最佳边或点集合。 这些知识点涵盖了算法竞赛中常见的问题类型，是准备ACM竞赛或提升编程能力的重要参考资料。