各种公式及模板.doc

各种公式及模板 1、几何... 25 注意... 25 几何公式... 25 多边形... 27 多边形切割... 30 浮点函数... 31 面积... 36 球面... 37 三角形... 38 三维几何... 40 凸包... 47 网格... 49 圆... 49 整数函数... 51 2、组合... 54 组合公式... 54 排列组合生成... 54 生成 gray 码... 56 置换(polya) 56 字典序全排列... 57 字典序组合... 57 3、结构... 58 并查集... 58 堆... 59 线段树... 60 子段和... 65 子阵和... 65 4、数论... 66 阶乘最后非 0位... 66 模线性方程组... 67 素数... 68 欧拉函数... 69 5、数值计算... 70 定积分计算(Romberg) 70 多项式求根( 牛顿法) 72 周期性方程( 追赶法) 73 6、图论— NP 搜索... 74 最大团... 74 最大团(n<64)(faster) 75 7、图论—连通性... 77 无向图关键点(dfs 邻接阵) 77 无向图关键边(dfs 邻接阵) 78 无向图的块(bfs 邻接阵) 79 无向图连通分支(dfs/bfs 邻接阵) 80 有向图强连通分支(dfs/bfs 邻接阵) 81 有向图最小点基( 邻接阵) 82 8、图论—匹配... 83 二分图最大匹配(hungary 邻接表) 83 二分图最大匹配(hungary 邻接阵) 84 二分图最大匹配(hungary 正向表) 84 二分图最佳匹配(kuhn_munkras 邻接阵) 85 一般图匹配( 邻接表) 86 一般图匹配( 邻接阵) 87 一般图匹配( 正向表) 87 9、图论—网络流... 88 最大流( 邻接阵) 88 上下界最大流( 邻接阵) 89 上下界最小流( 邻接阵) 90 最大流无流量( 邻接阵) 91 最小费用最大流( 邻接阵) 91 10、图论—应用... 92 欧拉回路( 邻接阵) 92 树的前序表转化... 93 树的优化算法... 94 拓扑排序( 邻接阵) 95 最佳边割集... 96 最佳点割集... 97 最小边割集... 98 最小点割集... 99 最小路径覆盖... 101 11、图论—支撑树... 101 最小生成树(kruskal 邻接表) 101 最小生成树(kruskal 正向表) 103 最小生成树(prim+binary_heap 邻接表) 104 最小生成树(prim+binary_heap 正向表) 105 最小生成树(prim+mapped_heap 邻接表) 106 最小生成树(prim+mapped_heap 正向表) 108 最小生成树(prim 邻接阵) 109 最小树形图( 邻接阵) 109 12、图论—最短路径... 111 最短路径( 单源 bellman_ford 邻接阵) 111 最短路径( 单源 dijkstra+bfs 邻接表) 111 最短路径( 单源 dijkstra+bfs 正向表) 112 最短路径( 单源 dijkstra+binary_heap 邻接表) 113 最短路径( 单源 dijkstra+binary_heap 正向表) 114 最短路径( 单源 dijkstra+mapped_heap 邻接表) 115 最短路径( 单源 dijkstra+mapped_heap 正向表) 116 最短路径( 单源 dijkstra 邻接阵) 117 最短路径( 多源 floyd_warshall 邻接阵) 118 13、应用... 118 Joseph 问题... 118 N 皇后构造解... 119 布尔母函数... 120 第k 元素... 120 幻方构造... 121 模式匹配(kmp