浙江大学ACM竞赛模板：几何与图论算法库

"这份资源是浙江大学ACM竞赛团队的常用模板集合，由WishingBone整理并在2002年发布，后由Riveria在2004年进行了更新。这个模板库涵盖了广泛的算法和数据结构，特别强调了几何和图论问题的解决方案，非常适合参加ACM竞赛或进行算法学习的人员使用。" 详细内容： 1. 几何部分提供了丰富的算法，包括基本的几何公式、多边形处理（如切割和计算面积）、浮点函数、球面几何、三角形计算以及三维几何问题的解决。此外，还有关于凸包、网格处理、圆的计算以及整数函数的实现，这些都对处理图形和空间问题非常有帮助。 2. 组合数学部分包含了常用的组合公式，可以生成排列组合序列，以及Gray码、Polya计数、字典序排列和组合的算法，这些都是解决组合优化问题的基础工具。 3. 结构部分介绍了几种重要的数据结构，如并查集用于处理集合的合并与查询，堆用于高效地维护最大或最小元素，线段树则支持区间查询和修改操作，子段和与子阵和处理区间和问题，这些都是动态数据查询的关键。 4. 数论部分包含了一些基础但重要的概念，如计算阶乘的最后非零位、模线性方程组的解法、素数检测以及欧拉函数的计算，这些都是数论算法的基础。 5. 数值计算部分提供了定积分的Romberg方法、多项式求根的牛顿法以及周期性方程的追赶法，这些对于数值计算和近似解问题十分实用。 6. 图论部分主要涉及NP搜索问题，如最大团的算法，以及连通性的判断和关键点、边的检测。此外，还包括有向图的强连通分支、最小点基等高级概念。 7. 匹配部分介绍了二分图的最大匹配算法，如匈牙利算法的不同实现，以及一般图的匹配策略，这些都是网络优化问题的重要工具。 8. 网络流部分涵盖了最大流、上下界最大流、最小费用最大流等算法，这些对于解决流量分配和资源调度问题极其关键。 9. 图论的应用部分包括了欧拉回路的检测、树的前序表转化、树的优化算法、拓扑排序以及最佳边割集和点割集的寻找，这些都是图论在实际问题中的应用实例。 总结来说，这个模板库是ACM竞赛选手和算法爱好者的宝贵资源，它包含了从基础到高级的各种算法，对提升几何、组合、数据结构、数论、数值计算和图论问题的解决能力有着极大的帮助。