浙江大学ACM竞赛程序库：几何、组合、图论与数论算法

"浙大ACM程序模板(c/c++)" 是浙江大学ICPCTeam开发的一套用于ACM竞赛的C/C++程序库，由WishingBone创建并在2004年由Riveria更新。这个模板库包含了丰富的算法和数据结构，适用于解决各种算法竞赛中的问题。 1、几何：这部分提供了处理几何问题的模板，包括基础的几何公式、多边形操作（如切割），浮点数处理、面积计算、球面几何、三角形计算以及三维几何问题的解决方案。还有凸包算法、网格处理、圆的运算以及整数函数。 2、组合数学：涵盖了组合公式、排列组合的生成、Gray码生成、Polya计数（置换）以及字典序的全排列和组合，这些都是组合问题中常见的算法。 3、数据结构：包括了并查集、堆、线段树等高效的数据结构，用于处理集合操作、优先队列和区间查询等问题。此外，还有子段和与子阵和的计算，方便处理动态范围更新和查询。 4、数论：提供了计算阶乘最后非零位的方法、模线性方程组的解法、素数检测以及欧拉函数的实现，这些是数论问题中常用的基础工具。 5、数值计算：包括了定积分的Romberg方法、多项式求根的牛顿法以及周期性方程的追赶法，用于处理实际计算问题。 6、图论—NP搜索：提供了最大团问题的解法，特别是对于规模较小的问题有更快的算法。 7、图论—连通性：包含无向图的关键点、关键边、块的识别，以及无向图和有向图的连通分支和强连通分支的查找，还有有向图的最小点基算法。 8、图论—匹配：提供了多种二分图最大匹配的算法（如Kuhn-Munkres算法）以及一般图的匹配算法。 9、图论—网络流：实现了最大流算法、上下界最大流和最小流，以及最小费用最大流，这些都是网络流问题的核心算法。 10、图论—应用：包括了欧拉回路的检测、树的前序表转化、树的优化算法、拓扑排序、最佳边割集以及最短路径的计算。 这套模板库为参加ACM竞赛的选手提供了强大的工具，可以帮助他们快速解决各类算法问题，提高编程效率。通过理解和使用这些模板，参赛者可以更好地专注于问题的逻辑和算法设计，而不是基础实现。