ACM竞赛常用算法模板：几何、组合、图论与数值计算

"这份资源是浙江大学ICPC团队的日常练习库，由WishingBone于2002年创建，并在2004年由Riveria进行了最后更新。它包含了一系列ACM竞赛常用的算法模板，覆盖了从几何、组合数学、数据结构、数论到数值计算、图论等多个领域。" 1、几何 这一部分提供了处理几何问题的模板，包括基本的几何公式、多边形的处理（如多边形切割）、浮点函数的运算、面积计算、球面几何、三角形计算以及三维几何问题。还有关于凸包、网格、圆以及整数函数的模板，帮助解决各种几何问题。 2、组合 涵盖了组合数学的基础公式和操作，如组合的生成、Gray码、Polya计数法、字典序全排列和组合，为解决组合优化和计数问题提供了便利。 3、结构 提供了常见的数据结构模板，如并查集用于处理集合的合并与查询，堆实现优先队列，线段树用于区间查询和修改，子段和与子阵和处理数组的区间操作。 4、数论 包含了数论中的重要概念和算法，如阶乘最后非0位的计算、模线性方程组的解法、素数检测、欧拉函数的计算，这些都是解决数论问题的关键。 5、数值计算 提供了数值计算的模板，如Romberg方法进行定积分计算，牛顿法求多项式根，以及周期性方程的求解。 6、图论—NP搜索 主要涉及NP完全问题，如最大团的计算，其中对于规模较小的问题有更快速的算法。 7、图论—连通性 包括无向图的关键点、关键边、块的检测，以及无向图和有向图的连通分支和强连通分支的查找。还有有向图的最小点基算法。 8、图论—匹配 提供了二分图最大匹配的各种算法实现，如匈牙利算法的不同版本，以及一般图匹配的模板。 9、图论—网络流 包括最大流算法及其变种，如上下界最大流、最小费用最大流等，都是解决网络流问题的重要工具。 10、图论—应用 这部分包括了特定问题的算法，如欧拉回路的检测、树的前序表转化、树的优化算法、拓扑排序以及最佳边割集和最佳点割集的求解。 这些模板是ACM竞赛选手和算法工程师的宝贵资源，可以帮助快速理解和实现各种算法，提高解题效率。