浙江大学ACM竞赛代码库：几何、组合、图论算法大全

"浙江大学ACM模板是一个集合了经典代码的资源库，主要针对ACM（国际大学生程序设计竞赛）的学习和参考。这个模板由WishingBone于2002年创建，并在2004年由Riveria进行了最后更新。它包含了一系列与算法和数据结构相关的模块，覆盖了从几何到数论，再到图论等多个领域，是ACMer提高编程技能和解决竞赛问题的重要参考资料。" 以下是浙江大学ACM模板中的主要知识点详解： 1. 几何： - 包含几何公式、多边形处理、多边形切割、浮点函数、面积计算、球面几何、三角形处理、三维几何、凸包计算、网格处理、圆的算法以及整数函数。 2. 组合： - 提供了组合公式、排列组合生成、Gray码生成、Polya计数（置换）算法、字典序全排列和组合计算。 3. 结构： - 实现了并查集、堆、线段树（用于区间查询和修改）、子段和与子阵和的高效算法。 4. 数论： - 阶乘最后非0位的计算、模线性方程组求解、素数检测、欧拉函数的实现。 5. 数值计算： - 定积分的Romberg方法、多项式求根的牛顿法、周期性方程的追赶法求解。 6. 图论—NP搜索： - 最大团问题的算法，包括n小于64时的优化版本。 7. 图论—连通性： - 无向图的关键点和关键边、无向图的块、无向图和有向图的连通分支、有向图的强连通分支、有向图的最小点基。 8. 图论—匹配： - 二分图的最大匹配算法（Kuhn-Munkres和匈牙利算法）、一般图的匹配算法。 9. 图论—网络流： - 包括最大流算法、上下界最大流、最小流、无流量最大流以及最小费用最大流。 10. 图论—应用： - 欧拉回路的查找、树的前序表转化、树的优化算法、拓扑排序、最佳边割集和最佳点割集的计算。 这些内容不仅涵盖了ACM竞赛中常见的基础算法，还涉及了许多高级主题，对于参赛者来说，这是一个宝贵的自学和实践资源。通过深入理解和掌握这些算法，可以有效提升解决复杂编程问题的能力。