浙江大学ACM模板.doc

《浙江大学ACM模板.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、ZhejiangUniversityICPCTeamRoutineLibrarybyWishingBone(Dec.2002)LastUpdate(Nov.2004)byRiveria1、几何251.1注意251.2几何公式251.3多边形271.4多边形切割301.5浮点函数311.6面积361.7球面371.8三角形381.9三维几何401.10凸包471.11网格491.12圆491.13整数函数512、组合54932.1组合公式542.2排列组合生成542.3生成gray码562.4置换(poly

2、a)562.5字典序全排列572.6字典序组合573、结构583.1并查集583.2堆593.3线段树603.4子段和653.5子阵和654、数论664.1阶乘最后非0位664.2模线性方程组674.3素数684.4欧拉函数695、数值计算705.1定积分计算(Romberg)705.2多项式求根(牛顿法)725.3周期性方程(追赶法)736、图论—NP搜索746.1最大团746.2最大团(n<64)(faster)757、图论—连通性777.1无向图关键点(dfs邻接阵)777.2无向图关键边(dfs邻

3、接阵)787.3无向图的块(bfs邻接阵)797.4无向图连通分支(dfs/bfs邻接阵)807.5有向图强连通分支(dfs/bfs邻接阵)817.6有向图最小点基(邻接阵)828、图论—匹配838.1二分图最大匹配(hungary邻接表)838.2二分图最大匹配(hungary邻接阵)848.3二分图最大匹配(hungary正向表)848.4二分图最佳匹配(kuhn_munkras邻接阵)858.5一般图匹配(邻接表)868.6一般图匹配(邻接阵)878.7一般图匹配(正向表)879、图论—网络流889

4、.1最大流(邻接阵)889.2上下界最大流(邻接阵)899.3上下界最小流(邻接阵)909.4最大流无流量(邻接阵)919.5最小费用最大流(邻接阵)9110、图论—应用9210.1欧拉回路(邻接阵)9210.2树的前序表转化9310.3树的优化算法9410.4拓扑排序(邻接阵)9510.5最佳边割集9610.6最佳点割集9710.7最小边割集989310.8最小点割集9910.9最小路径覆盖10111、图论—支撑树10111.1最小生成树(kruskal邻接表)10111.2最小生成树(kruskal正

5、向表)10311.3最小生成树(prim+binary_heap邻接表)10411.4最小生成树(prim+binary_heap正向表)10511.5最小生成树(prim+mapped_heap邻接表)10611.6最小生成树(prim+mapped_heap正向表)10811.7最小生成树(prim邻接阵)10911.8最小树形图(邻接阵)10912、图论—最短路径11112.1最短路径(单源bellman_ford邻接阵)11112.2最短路径(单源dijkstra+bfs邻接表)11112.3最短

6、路径(单源dijkstra+bfs正向表)11212.4最短路径(单源dijkstra+binary_heap邻接表)11312.5最短路径(单源dijkstra+binary_heap正向表)11412.6最短路径(单源dijkstra+mapped_heap邻接表)11512.7最短路径(单源dijkstra+mapped_heap正向表)11612.8最短路径(单源dijkstra邻接阵)11712.9最短路径(多源floyd_warshall邻接阵)11813、应用11813.1Joseph问题1

7、1813.2N皇后构造解11913.3布尔母函数12013.4第k元素12013.5幻方构造12113.6模式匹配(kmp)12213.7逆序对数12313.8字符串最小表示12313.9最长公共单调子序列12413.10最长子序列12513.11最大子串匹配12613.12最大子段和12713.13最大子阵和12714、其它12814.1大数(只能处理正数)12814.2分数13414.3矩阵13614.4线性方程组13814.5线性相关14014.6日期140931、几何1.1注意1.注意舍入方式(0

8、.5的舍入方向);防止输出-0.2.几何题注意多测试不对称数据.3.整数几何注意xmult和dmult是否会出界;符点几何注意eps的使用.4.避免使用斜率;注意除数是否会为0.5.公式一定要化简后再代入.6.判断同一个2*PI域内两角度差应该是abs(a1-a2)

9、

10、abs(a1-a2)>pi+pi-beta;相等应该是abs(a1-a2)

11、

12、abs(a1-a2)>pi+pi-eps;7.需要的话尽量使用a