程序设计竞赛训练营:算法与实践

第 1章 回溯法 1
1．1　八皇后问题　1
1．2　搜索　10
1．2．1　单向搜索　10
1．2．2　双向搜索　16
1．3　剪枝　17
1．3．1　正方形剖分　26
1．3．2　关灯问题　27
1．4　15数码问题　29
1．5　小结　38
第　2章 图遍历　39
2．1　基本概念　39
2．1．1　图的属性　39
2．1．2　欧拉公式　40
2．1．3　路与连通　40
2．2　图的表示　41
2．2．1　邻接矩阵　41
2．2．2　边列表和前向星　41
2．2．3　邻接表　42
2．2．4　链式前向星　43
2．3　图遍历　44
2．3．1　广度优先遍历　44
2．3．2　深度优先遍历　50
2．4　图遍历的应用　53
2．4．1　图的连通性　53
2．4．2　*短路径　54
2．4．3　*长简单路径　56
2．4．4　图的着色　57
2．4．5　*近公共祖先　57
2．4．6　割顶　65
2．4．7　割边　68
2．4．8　强连通分支　70
2．4．9　半连通分支　77
2．4．10　2-SAT　78
2．4．11　图的直径　83
2．4．12　树的重心　84
2．5　拓扑排序　85
2．6　小结　87
第3章　图算法　89
3．1　基本概念　89
3．2　图的回路　90
3．2．1　欧拉回　90
3．2．2　中国投递员问题　104
3．2．3　哈密顿回　105
3．2．4　旅行商问题　107
3．3　*小生成树　107
3．3．1　Prim算法　107
3．3．2　Kruskal算法　109
3．3．3　*小生成树的扩展问题　111
3．3．4　度限制*小生成树　111
3．3．5　次*优*小生成树　114
3．4　*短路径问题　118
3．4．1　Moore-Dijkstra算法　118
3．4．2　Bellman-Ford算法　126
3．4．3　Floyd-Warshall算法　130
3．4．4　传递闭包　132
3．4．5　*小化的*大距离　134
3．4．6　差分约束系统　134
3．4．7　第K短路径问题　138
3．5　网络流问题　140
3．5．1　基本概念　141
3．5．2　Ford-Fulkerson方法　142
3．5．3　Edmonds-Karp算法　144
3．5．4　Dinic算法　149
3．5．5　ISAP算法　153
3．5．6　*小截问题　158
3．5．7　*小费用*大流问题　159
3．6　边独立集与二部图匹配　161
3．6．1　网络流解法　162
3．6．2　Hungarian算法　164
3．6．3　Hopcroft-Karp算法　169
3．6．4　Gale-Shapley算法　171
3．6．5　Edmonds算法　172
3．7　二部图加权完备匹配　176
3．7．1　网络流解法　176
3．7．2　Kuhn-Munkres算法　177
3．8　点支配集、点覆盖集、点独立集　185
3．8．1　点支配集　185
3．8．2　点覆盖集　185
3．8．3　点独立集与*大团　188
3．9　路径覆盖和边覆盖　188
3．9．1　*小路径覆盖　188
3．9．2　*小边覆盖　189
3．10　树的相关问题求解　189
3．10．1　*小点支配　189
3．10．2　*小点覆盖　190
3．10．3　*大点独立　191
3．11　小结　191
第4章　动态规划　193
4．1　背包问题　193
4．1．1　01背包问题　193
4．1．2　完全背包问题　197
4．1．3　多重背包问题　197
4．1．4　背包问题扩展　198
4．2　备忘　200
4．2．1　3n + 1问题　201
4．2．2　正交范围查询　203
4．2．3　*大正方形（长方形）　203
4．2．4　整数划分　206
4．2．5　博弈树　206
4．2．6　备忘与递推　210
4．3　松弛　217
4．3．1　Moore-Dijkstra算法　218
4．3．2　Bellman-Ford算法　220
4．3．3　Floyd-Warshall算法　220
4．4　集合型动态规划　222
4．5　区间型动态规划　229
4．5．1　矩阵链乘法　229
4．5．2　石子合并问题　231
4．6　图论型动态规划　238
4．6．1　路径计数　241
4．6．2　树形动态规划　243
4．6．3　旅行商问题　246
4．6．4　双调欧几里得旅行商问题　247
4．7　概率型动态规划　250
4．8　非典型动态规划　255
4．9　动态规划的优化　257
4．9．1　空间优化　257
4．9．2　状态优化　258
4．9．3　二进制优化　262
4．9．4　单调队列优化　262
4．9．5　斜率优化　265
4．9．6　四边形不等式优化　268
4．10　子序列和子串问题　271
4．10．1　*短编辑距离　271
4．10．2　*长公共子序列　274
4．10．3　*长公共子串　276
4．10．4　*长递增子序列　277
4．10．5　*长不重复子串　280
4．10．6　*长回文子串　281
4．10．7　*大连续子序列和（积）　285
4．11　贪心算法　287
4．11．1　部分背包问题　288
4．11．2　纸币找零问题　289
4．11．3　硬币兑换问题　292
4．11．4　霍夫曼编码　293
4．11．5　*优策略选择　295
4．12　小结　296
第5章　网格　297
5．1　矩形网格　297
5．1．1　网格行走　297
5．1．2　Flood-Fill算法　299
5．1．3　国际象棋棋盘　302
5．1．4　骑士周游问题　304
5．2　三角形网格　309
5．3　六边形网格　312
5．4　经度与纬度　312
5．5　小结　313
附录A　如何使用UVa OJ　314
附录B　ASCII表　317
附录C　C++运算符优先级　318
附录D　习题索引　319
参考资料　320