清华大学ACM代码模板集：几何、组合、结构与图论算法

"ACM模板大全-清华大学" 是一份汇集了算法竞赛（ACM）常用模板的资料，主要由清华大学整理提供，包含几何、组合、结构、数论、数值计算、图论等多个方面的算法模板，旨在帮助参赛者快速解决各类问题。 1. 几何： - 注意：在处理几何问题时，需特别关注精度问题，避免浮点数运算导致的误差。 - 几何公式：涉及点、线、面之间的关系，如距离、夹角、交点计算等。 - 多边形：包括点在多边形内的判断、多边形面积计算等。 - 多边形切割：处理多边形被其他形状分割的问题。 - 浮点函数：处理浮点数相关的运算，可能需要用到高精度计算库。 - 面积：计算各种几何图形的面积，如矩形、圆形、三角形等。 - 球面：涉及球体上的坐标转换、球面距离计算等。 - 三角形：包括三角函数的应用，如余弦定理、正弦定理等。 - 三维几何：处理三维空间中的几何问题，如点、线、面的关系，体积计算等。 - 凸包：快速计算点集的凸包，如Graham扫描法、Jarvis步进法等。 - 网格：处理格点上的几何问题，如格点覆盖、格点路径规划等。 - 圆：圆的性质及圆上的点、线段的处理。 2. 组合： - 组合公式：如组合数C(n, k)的计算。 - 排列组合生成：生成所有可能的排列或组合序列。 - Gray码：生成无相邻位翻转的二进制序列。 - 置换(Polya)：用于处理置换问题，如排列的字典序计算。 - 字典序全排列：生成具有字典序的全排列序列。 - 字典序组合：生成具有字典序的组合序列。 3. 结构： - 并查集：处理集合合并与查询问题，常用于树形结构的维护。 - 堆：包括大顶堆和小顶堆，用于优先队列的实现。 - 线段树：处理区间查询和修改操作，如区间求和、最值等问题。 - 子段和：快速计算一段连续序列的和。 - 子阵和：处理二维矩阵的子区域和。 4. 数论： - 阶乘最后非0位：计算阶乘结果末尾非零数字的数量。 - 模线性方程组：解模线性方程组，如扩展欧几里得算法。 - 素数：素数检测和素数生成，如埃拉托斯特尼筛法。 - 欧拉函数：计算小于等于n且与n互质的数的数量。 5. 数值计算： - 定积分计算：如Romberg方法，用于数值积分。 - 多项式求根：牛顿迭代法求多项式的实根或复根。 - 周期性方程：利用追赶法求解周期性方程。 6. 图论—NP搜索： - 最大团：寻找图中最大的完全子图。 - n<64的最大团优化算法：针对小规模问题的高效解决方案。 7. 图论—连通性： - 无向图关键点：确定图中影响连通性的节点。 - 无向图关键边：找出维持图连通性的边。 - 无向图的块：识别图的连通分支结构。 - 无向图连通分支：遍历所有的连通分支。 - 有向图强连通分支：找到图中的强连通分量。 - 有向图最小点基：求解图的最小点基问题。 8. 图论—匹配： - 二分图最大匹配：Kuhn-Munkres算法（匈牙利算法）解决二分图的最大匹配问题。 - 一般图匹配：处理非二分图的匹配问题。 9. 图论—网络流： - 最大流：寻找网络中从源点到汇点的最大流量。 - 上下界最大流/最小流：处理带有上下界限制的网络流问题。 - 最小费用最大流：在保证最大流量的同时，最小化总费用。 这份模板大全是ACM竞赛选手的重要参考资料，涵盖了算法竞赛中常见的问题类型和解决策略，对于提高解题效率和准确度有着极大的帮助。