浙江大学acm模板

《浙江大学acm模板》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、ZhejiangUniversityICPCTeamRoutineLibrarybyWishingBone(Dec.2002)2471.几何1.1.注意1.2.几何公式1.3.多边形1.4.多边形切割1.5.浮点函数1.6.面积1.7.球面1.8.三角形1.9.三维几何1.10.凸包1.11.网格1.12.圆1.13.整数函数2.组合2.1组合公式2.2排列组合生成2.3生成gray码2472.4置换(polya)2.5字典序全排列2.6字典序组合3.结构3.1并查集3.2堆3.3线段树3.4子段和3.5子阵和4.数论4.1阶乘最后非0位4.2模线性方程组4.3素数4.4欧拉函数5

2、.数值计算5.1定积分计算(Romberg)5.2多项式求根(牛顿法)5.3周期性方程(追赶法)2476.图论—NP搜索6.1最大团6.2最大团(n<64)(faster)7.图论—连通性7.1无向图关键点(dfs邻接阵)7.2无向图关键边(dfs邻接阵)7.3无向图的块(bfs邻接阵)7.4无向图连通分支(dfs/bfs邻接阵)7.5有向图强连通分支(dfs/bfs邻接阵)7.6有向图最小点基(邻接阵)8.图论—匹配8.1二分图最大匹配(hungary邻接表)8.2二分图最大匹配(hungary邻接阵)8.3二分图最大匹配(hungary正向表)8.4二分图最佳匹配(kuhn_m

3、unkras邻接阵)8.5一般图匹配(邻接表)8.6一般图匹配(邻接阵)8.7一般图匹配(正向表)2479.图论—网络流9.1最大流(邻接阵)9.2上下界最大流(邻接阵)9.3上下界最小流(邻接阵)9.4最大流无流量(邻接阵)9.5最小费用最大流(邻接阵)10.图论—应用10.1欧拉回路(邻接阵)10.2树的前序表转化10.3树的优化算法10.4拓扑排序(邻接阵)10.5最佳边割集10.6最佳点割集10.7最小边割集10.8最小点割集10.9最小路径覆盖11.图论—支撑树11.1最小生成树(kruskal邻接表)24711.2最小生成树(kruskal正向表)11.3最小生成树(p

4、rim+binary_heap邻接表)11.4最小生成树(prim+binary_heap正向表)11.5最小生成树(prim+mapped_heap邻接表)11.6最小生成树(prim+mapped_heap正向表)11.7最小生成树(prim邻接阵)11.8最小树形图(邻接阵)12.图论—最短路径12.1最短路径(单源bellman_ford邻接阵)12.2最短路径(单源dijkstra+bfs邻接表)12.3最短路径(单源dijkstra+bfs正向表)12.4最短路径(单源dijkstra+binary_heap邻接表)12.5最短路径(单源dijkstra+binary_

5、heap正向表)12.6最短路径(单源dijkstra+mapped_heap邻接表)12.7最短路径(单源dijkstra+mapped_heap正向表)12.8最短路径(单源dijkstra邻接阵)12.9最短路径(多源floyd_warshall邻接阵)13.应用24713.1Joseph问题13.2N皇后构造解13.3布尔母函数13.4第k元素13.5幻方构造13.6模式匹配(kmp)13.7逆序对数13.8字符串最小表示13.9最长公共单调子序列13.10最长子序列13.11最大子串匹配13.12最大子段和13.13最大子阵和其它14.1大数(只能处理正数)14.2分数1

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

7、

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

9、

10、abs(a1-a2)>pi+pi-eps;7.需要的话尽量使用atan2,注意:atan2(0,0)=0,247a

11、tan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.8.crossproduct=

12、u

13、*

14、v

15、*sin(a)dotproduct=

16、u

17、*

18、v

19、*cos(a)9.(P1-P0)x(P2-P0)结果的意义:正:在顺时针(0,pi)内负:在逆时针(0,pi)内0:,共线,夹角为0或pi10.误差限缺省使用1e-8!1.