国际大学生程序设计竞赛例题解3 （附光盘）

　　第1章　图论相关知识和基本算法
　　1.1　图的基本概念
　　1.2　图的邻接矩阵表示和邻接表表示
　　1.3　拓扑排序
　　1.4　连通分量
　　1.5　2一连通分量
　　1.6　最短路
　　1.6.1　非负边权的单源最短路
　　1.6.2　任意边权的单源最短路
　　1.6.3　任意边权的所有顶点之间的最短路
　　1.7　最大流
　　1.8　二分图最大匹配
　　第2章　图论例题分析
　　2.1　删边问题
　　2.1.1　题目描述
　　2.1.2　题目分析及算法实现
　　2.1.3　参考程序及程序分析
　　2.1.4　测试数据及输出结果
　　2.2　烦人的幻灯片问题
　　2.2.1　题目描述
　　2.2.2　题目分析及算法实现
　　2.2.3　参考程序及程序分析
　　2.2.4　测试数据及输出结果
　　2.3　字母排序问题
　　2.3.1　题目描述
　　2.3.2　题目分析及算法实现
　　2.3.3　参考程序及程序分析
　　2.3.4　测试数据及输出结果
　　2.4　投递问题
　　2.4.1　题目描述
　　2.4.2　题目分析及算法实现
　　2.4.3　参考程序及程序分析
　　2.4.4　测试数据及输出结果
　　2.5　银河贸易问题
　　2.5.1　题目描述
　　2.5.2　题目分析及算法实现
　　2.5.3　参考程序及程序分析
　　2.5.4　测试数据及输出结果
　　2.6　安全网络问题
　　2.6.1　题目描述
　　2.6.2　题目分析及算法实现
　　2.6.3　参考程序及程序分析
　　2.6.4　测试数据与输出结果
　　2.7　交通问题
　　2.7.1　题目描述
　　2.7.2　题目分析及算法实坝
　　2.7.3　参考程序及程序分析
　　2.7.4　测试数据及输出结果
　　2.8　单行道问题
　　2.8.1　题目描述
　　2.8.2　题目分析及算法实现
　　2.8.3　参考程序及程序分析
　　2.8.4　测试数据及输出结果
　　2.9　UNⅨ的插头问题
　　2.9.1　题目描述
　　2.9.2　题目分析及算法实现
　　2.9.3　参考程序及程序分析
　　2.9.4　测试数据及输出结果
　　2.10　进化树问题
　　2.10.1　题目描述
　　2.10.2　题目分析及算法实现
　　2.10.3　参考程序及程序分析
　　2.10.4　测试数据及输出结果
　　2.11　破坏行动问题
　　2.11.1　题目描述
　　2.11.2　题目分析及算法实现
　　2.11.3　参考程序及程序分析
　　2.11.4　测试数据及输出结果
　　2.12　街道的方向问题
　　2.12.1　题目描述
　　2.12.2　题目分析及算法实坝
　　2.12.3　参考程序及程序分析
　　2.12.4　测试数据及输出结果
　　……
　　第3章　动态规划
　　第4章　动态规划例题分析
　　第5章　综合题例题分析
　　参考文献
　　作者简介

　　郭嵩山，男，1945年4月出生，1967年毕业于上海交通大学无线电技术专业，中山大学信息科学与技术学院计算机科学系教授，主要从事计算机操作系统的教学和研究。
　　主要著作有电子工业出版社出版的《BIO结构分析教程》、《DOS内核结构分析教程》、《COMMAND结构分析教程》、《Windows9810结构分析教程》、《国际大学生程序设计竞赛例题解（一）数论、计算几何、搜索算法专集》，《国际大学生程序设计竞赛例题解（二）广东省大学生程序设计竞赛试题解（2003—2005年）》，人民邮电出版社出版的《数据结构及其应用》，中山大学出版社出版的《青少年信息学奥林匹克竞赛广东试题及解答（1986—1994）》，北京大学出版社出版的《国际大学生程序设计竞赛辅导教程》等。
　　近几年，担任ACM国际大学生程序设计竞赛（ACM/ICPC）广东省赛区执行主席，主持了五届ACM/ICPC广东省赛。在科研方面，指导多名硕士研究生在人工智能算法研究方面取得较好的成果。

　　本书以图论、动态规划算法、综合题的形式介绍了ACM国际大学生程序设计竞赛（ACM/ICPC）中所用到的典型算法，并结合例题，对如何灵活地运用这些算法进行比较详细分析和深入浅出的讲解。本书以精讲多练为教学宗旨，并在每一个专题论述后用一章的篇幅选出一批有代表性的竞赛例题，对每道例题都有详细的解题的分析、基本的测试数据以及答案，以便同学们能在了解基本算法后作为学习、训练之用。随书附带的光盘里存放了所有例题中完整的测试数据，以便于有更高、更严格要求的同学能利用规模更大的测试数据进行训练和学习。
　　本书可以作为高等院校有关专业的研究生和本科学生参加国际大学生程序设计竞赛的辅导教材，也可作为高等院校有关专业课程的教材和教学参考书，还可作为中学青少年信息学奥林匹克竞赛省级及省级以上优秀选手备战信息奥林匹克竞赛的培训教材及训练题集。