ACM程序设计竞赛基础教程

3.1.2 并查集简介31
3.1.3 树状数组简介31
3.2 实例分析32
第4章 字符串43
4.1 字符串匹配43
4.1.1 朴素的字符串匹配算法43
4.1.2 KMP算法44
4.1.3 其他匹配算法44
4.2 实例分析44
4.3 小结50
第5章 搜索算法51
5.1 基本搜索算法51
5.1.1 递归与迭代51
5.1.2 深度优先搜索与广度优先搜索51
5.1.3 回溯51
5.2 搜索算法的一些优化52
5.2.1 剪枝函数52
5.2.2 双向广度搜索52
5.3 实例分析52
5.4 小结67
第6章 图论算法68
6.1 最短路径68
6.1.1 Dijkstra算法68
6.1.2 Floyd算法69
6.1.3 Bellman-Ford算法69
6.2 最小生成树70
6.2.1 Kruskal算法71
6.2.2 Prim算法72
6.3 最大匹配--匈牙利算法73
6.4 最优权匹配问题74
6.4.1 理论基础74
6.4.2 基本思想75
6.4.3 样例代码75
6.5 割点、割边以及连通分量77
6.5.1 理论基础77
6.5.2 求割点78
6.5.3 求强连通分量79
6.6 网络流81
6.6.1 理论基础81
6.6.2 最大流问题81
6.6.3 最小费用最大流问题83
6.7 实例分析84
6.8 小结106
第7章 动态规划算法107
7.1 基本思想109
7.2 基本概念109
7.3 基本原理110
7.3.1 最优化原理110
7.3.2 无后效性110
7.4 基本步骤110
7.5 经典例子111
7.6 实例分析115
7.7 小结135
第8章 计算几何基础136
8.1 矢量136
8.1.1 矢量的概念136
8.1.2 矢量加减法136
8.1.3 矢量叉积136
8.1.4 矢量叉积的应用136
8.2 包含关系138
8.2.1 判断图形是否包含在矩形中138
8.2.2 判断图形是否包含在多边形中138
8.2.3 判断图形是否包含在圆中 141
8.3 凸包141
8.3.1 凸包的概念141
8.3.2 凸包的求法141
8.4 实例分析143
第9章 数论160
9.1 基本数学算法160
9.1.1 素数筛选160
9.1.2 最大公约数160
9.1.3 快速乘方161
9.2 实例分析161
附录A 综合训练题186
A.1 LuckyBird186
A.2 Josephus' problem187
A.3 Counter Strike189
A.4 Gauss Elimination192
A.5 The Math Problem193
A.6 Mobile phones194
A.7 Japan197
A.8 骨灰级玩家考证篇199
A.9 括号匹配202
A.10 食物链204