ACM模板(浙大版)

《ACM模板(浙大版)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录一．几何41.1注意41.2几何公式41.3多边形61.4多边形切割91.5浮点函数101.6面积151.7球面161.8三角形171.9三维几何191.10凸包271.11网格281.12圆281.13整数函数30二．组合332.1组合公式332.2排列组合生成332.3生成gray码352.4置换(polya)352.5字典序全排列362.6字典序组合36三．结构373.1并查集373.2堆383.3线段树393.4子段和443.5子阵和45四．数论454.1阶乘最后非0位454.2模线性方程组464.3素

2、数474.4欧拉函数494.5定积分计算(Romberg)494.6多项式求根(牛顿法)514.7周期性方程(追赶法)52五．图论535.1NP搜索531215.1.1最大团535.1.2最大团(n<64)(faster)545.2连通性565.2.1无向图关键点(dfs邻接阵)565.2.2无向图关键边(dfs邻接阵)575.2.3无向图的块(bfs邻接阵)585.2.4无向图连通分支(dfs/bfs邻接阵)595.2.5有向图强连通分支(dfs/bfs邻接阵)605.2.6有向图最小点基(邻接阵)625.3匹配

3、625.3.1二分图最大匹配(hungary邻接表)625.3.2二分图最大匹配(hungary邻接阵)635.3.3二分图最大匹配(hungary正向表)635.3.4二分图最佳匹配(kuhn_munkras邻接阵)645.3.5一般图匹配(邻接表)655.3.6一般图匹配(邻接阵)665.3.7一般图匹配(正向表)675.4网络流685.4.1最大流(邻接阵)685.4.2上下界最大流(邻接阵)695.4.3上下界最小流(邻接阵)695.4.4最大流无流量(邻接阵)705.4.5最小费用最大流(邻接阵)715.

4、5应用725.5.1欧拉回路(邻接阵)725.5.2树的前序表转化725.5.3树的优化算法735.5.4拓扑排序(邻接阵)755.5.5最佳边割集755.5.6最佳点割集765.5.7最小边割集785.5.8最小点割集795.5.9最小路径覆盖805.6支撑树815.6.1最小生成树(kruskal邻接表)815.6.2最小生成树(kruskal正向表)825.6.3最小生成树(prim+binary_heap邻接表)835.6.4最小生成树(prim+binary_heap正向表)855.6.5最小生成树(pr

5、im+mapped_heap邻接表)865.6.6最小生成树(prim+mapped_heap正向表)875.6.7最小生成树(prim邻接阵)885.6.8最小树形图(邻接阵)895.7最短路径905.7.1最短路径(单源bellman_ford邻接阵)901215.7.2最短路径(单源dijkstra+bfs邻接表)915.7.3最短路径(单源dijkstra+bfs正向表)915.7.4最短路径(单源dijkstra+binary_heap邻接表)925.7.5最短路径(单源dijkstra+binary_h

6、eap正向表)935.7.6最短路径(单源dijkstra+mapped_heap邻接表)945.7.7最短路径(单源dijkstra+mapped_heap正向表)955.7.8最短路径(单源dijkstra邻接阵)965.7.9最短路径(多源floyd_warshall邻接阵)97六．应用986.1Joseph问题986.2N皇后构造解986.3布尔母函数996.4第k元素1006.5幻方构造1006.6模式匹配(kmp)1016.7逆序对数1026.8字符串最小表示1026.9最长公共单调子序列1036.10

7、最长子序列1046.11最大子串匹配1056.12最大子段和1066.13最大子阵和107七．其它1087.1大数(只能处理正数)1087.2分数1137.3矩阵1157.4线性方程组1177.5线性相关1197.6日期120121一．几何1.1注意1.注意舍入方式(0.5的舍入方向);防止输出-0.2.几何题注意多测试不对称数据.3.整数几何注意xmult和dmult是否会出界;符点几何注意eps的使用.4.避免使用斜率;注意除数是否会为0.5.公式一定要化简后再代入.6.判断同一个2*PI域内两角度差应该是ab

8、s(a1-a2)

9、

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

11、

12、abs(a1-a2)>pi+pi-eps;7.需要的话尽量使用atan2,注意:atan2(0,0)=0,atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.8.cross