浙江大学ACM模板（经典代码）

【实例简介】

ICPC，大学生ACM竞赛经典模板

【实例截图】备战ACM

【核心代码】

1、 几何.........................................................................................................................19
1.1 注意.................................................................................................................19
1.2 几何公式.........................................................................................................19
1.3 多边形.............................................................................................................21
1.4 多边形切割.....................................................................................................24
1.5 浮点函数.........................................................................................................25
1.6 面积.................................................................................................................30
1.7 球面.................................................................................................................31
1.8 三角形.............................................................................................................32
1.9 三维几何.........................................................................................................34
1.10 凸包.................................................................................................................41
1.11 网格.................................................................................................................43
1.12 圆.....................................................................................................................43
1.13 整数函数.........................................................................................................45
2、 组合.........................................................................................................................48
2.1 组合公式..................................................................................................................48
2.2 排列组合生成..........................................................................................................48
2.3 生成 gray 码.............................................................................................................50
2.4 置换(polya)..............................................................................................................50
2.5 字典序全排列..........................................................................................................51
2.6 字典序组合513 、
结 构
.........................................................................................................................................52
3.1 并查集......................................................................................................................52
3.2 堆..............................................................................................................................53
3.3 线段树......................................................................................................................54
3.4 子段和......................................................................................................................59
3.5 子阵和594 、
数 论
.........................................................................................................................................60
4.1 阶乘最后非 0 位......................................................................................................60
4.2 模线性方程组..........................................................................................................61
4.3 素数..........................................................................................................................62
4.4 欧拉函数635 、
数值计算
.........................................................................................................................................64
5.1 定积分计算(Romberg) ............................................................................................64
5.2 多项式求根(牛顿法)...............................................................................................66
5.3 周期性方程(追赶法)676 、
图 论 — NP 搜 索
.........................................................................................................................................68
6.1 最大团......................................................................................................................68
6.2 最大团(n<64)(faster)697 、
图 论 — 连通性
.........................................................................................................................................71
7.1 无向图关键点(dfs 邻接阵) .....................................................................................71
7.2 无向图关键边(dfs 邻接阵) .....................................................................................72
7.3 无向图的块(bfs 邻接阵) .........................................................................................73
7.4 无向图连通分支(dfs/bfs 邻接阵) ...........................................................................74
7.5 有向图强连通分支(dfs/bfs 邻接阵) .......................................................................75
7.6 有向图最小点基(邻接阵)768 、
图 论 — 匹 配
.........................................................................................................................................77
8.1 二分图最大匹配(hungary 邻接表).........................................................................77
8.2 二分图最大匹配(hungary 邻接阵).........................................................................78
8.3 二分图最大匹配(hungary 正向表).........................................................................78
8.4 二分图最佳匹配(kuhn_munkras 邻接阵) ...............................................................79
8.5 一般图匹配(邻接表)...............................................................................................80
4
8.6 一般图匹配(邻接阵)...............................................................................................81
8.7 一般图匹配(正向表)819 、
图 论 — 网络流
.........................................................................................................................................82
9.1 最大流(邻接阵).......................................................................................................82
9.2 上下界最大流(邻接阵)...........................................................................................83
9.3 上下界最小流(邻接阵)...........................................................................................84
9.4 最大流无流量(邻接阵)...........................................................................................85
9.5 最小费用最大流(邻接阵).......................................................................................85
10、 图论—应用.............................................................................................................86
10.1 欧拉回路(邻接阵).........................................................................................................86
10.2 树的前序表转化............................................................................................................87
10.3 树的优化算法................................................................................................................88
10.4 拓扑排序(邻接阵).........................................................................................................89
10.5 最佳边割集....................................................................................................................90
10.6 最佳点割集....................................................................................................................91
10.7 最小边割集....................................................................................................................92
10.8 最小点割集....................................................................................................................93
10.9 最小路径覆盖................................................................................................................95 
11、 图论—支撑树.........................................................................................................95
11.1 最小生成树(kruskal 邻接表).................................................................................95
11.2 最小生成树(kruskal 正向表).................................................................................97
11.3 最小生成树(prim binary_heap 邻接表)...............................................................98
11.4 最小生成树(prim binary_heap 正向表)...............................................................99
11.5 最小生成树(prim mapped_heap 邻接表) ..........................................................100
11.6 最小生成树(prim mapped_heap 正向表) ..........................................................102
11.7 最小生成树(prim 邻接阵)...................................................................................103
11.8 最小树形图(邻接阵) ...........................................................................................103
16
12、 图论—最短路径...................................................................................................105
12.1 最短路径(单源 bellman_ford 邻接阵)................................................................105
12.2 最短路径(单源 dijkstra bfs 邻接表)..................................................................105
12.3 最短路径(单源 dijkstra bfs 正向表)..................................................................106
12.4 最短路径(单源 dijkstra binary_heap 邻接表) ...................................................107
12.5 最短路径(单源 dijkstra binary_heap 正向表) ...................................................108
12.6 最短路径(单源 dijkstra mapped_heap 邻接表).................................................109
12.7 最短路径(单源 dijkstra mapped_heap 正向表).................................................110
12.8 最短路径(单源 dijkstra 邻接阵)......................................................................... 111
12.9 最短路径(多源 floyd_warshall 邻接阵) .............................................................112
17
13、 应用.......................................................................................................................112
13.1 Joseph 问题...........................................................................................................112
13.2 N 皇后构造解.......................................................................................................113
13.3 布尔母函数..........................................................................................................114
13.4 第 k 元素..............................................................................................................114
13.5 幻方构造..............................................................................................................115
13.6 模式匹配(kmp)....................................................................................................116
13.7 逆序对数..............................................................................................................117
13.8 字符串最小表示..................................................................................................117
13.9 最长公共单调子序列..........................................................................................118
13.10 最长子序列........................................................................................................119
13.11 最大子串匹配....................................................................................................120
13.12 最大子段和........................................................................................................121
13.13 最大子阵和........................................................................................................121
18