acm算法模版.doc

1、几何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组合542.1 组合公式542.2 排列组合生成542.3 生成gray码562.4 置换(polya)562.5 字典序全排列572.6 字典序组合57 3、结构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邻接阵)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.1 最大流(邻接阵)889.2 上下界最大流(邻接阵)899.3 上下界最小流(邻接阵)909.4 最大流无流量(邻接阵)919.5 最小费用最大流(邻接阵)9110、图论—应用9210.1 欧拉回路(邻接阵)9210.2 树的前序表转化9310.3 树的优化算法9410.4 拓扑排序(邻接阵)9510.5 最佳边割集9610.6 最佳点割集9710.7 最小边割集9810.8 最小点割集9910.9 最小路径覆盖10111、图论—支撑树10111.1 最小生成树(kruskal邻接表)10111.2 最小生成树(kruskal正向表)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 最短路径(单源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.1 Joseph问题11813.2 N皇后构造解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 日期140