编辑点评:
《挑战程序设计竞赛(第2版)》对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧
前言
如今,形形色色的程序设计竞赛层出不穷,听说过Google Code Jam、TopCoder、ACM-ICPC的读者恐怕不在少数。本书要介绍的正是这类以在规定时间内、又快又准地解决尽可能多的题目为目标的程序设计竞赛。
程序设计竞赛内涵丰富,即便是经验老道的程序员,要想在比赛中取得好成绩也绝非易事。要在程序设计竞赛中取胜,不仅需要运用灵活的想象和丰富的知识得出正确的算法,还需要一气呵成地实现并调试通过。
另一方面,程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣,大多数比赛都会准备若干面向初学者的题目。另外,即便未能在比赛中取得好成绩,通过比赛,也能够使自己的能力得到有效的锻炼。最重要的是,大家能够享受到激烈的比赛带来的乐趣。
本书的作者们参加过众多程序设计竞赛,在平时的练习和学习中,也获得了各种各样的知识与技巧,本书将这些知识技巧总结成册,主要介绍算法及其在相关问题中的应用。本书依照由易及难的顺序对问题进行讲解,章节的编排也参考了主题的难易程度及其相互的联系,内容较多的主题则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。
只要是具有编程基础知识的读者,均适合阅读本书。书中的源代码均用C++实现,不过只用到了其基本功能,所以即便读者不熟悉C++也不影响阅读。
世界规模的大赛-Google Code Jam(GCJ)
它是Google公司几乎每年都会举办的世界规模的程序设计竞赛,参赛者要在2-3小时内解决大约4道题。一旦从在线(Online)进行的几轮预选中胜出,就能够参加现场(Onsite)总决赛。该赛事的特点是,每道题都备有Small和Large两组输入数据。即便是难度系数较大的问题,只要输入规模足够小,依然可以简单地求解,这一形式深受广大参赛者的喜欢。另外,GCJ并不在服务器上自动执行程序,而是要求将源代码和本地执行的结果一同提交。
作者简介
★秋叶拓哉
Google Code Jam 2010 第9名
ACM-ICPC World Finals 2012 第11名
TopCoder Open 2012 Algorithm 第4名
昵称iwi
★岩田阳一
Google Code Jam 2009 第3名
TopCoder Open 2010 Marathon 冠军
IPSC 2010 个人组 冠军
昵称wata
★北川宜稔
ACM-ICPC World Finals 2010第16名
昵称kita_masa
译者简介:
★巫泽俊
ACM-ICPC World Finals 2009 第6名
ACM-ICPC World Finals 2011 冠军
Google Code Jam 2012 第7名
昵称watashi和rejudge
★庄俊元
ACM-ICPC Asia Phuket Regional 2011 冠军
2012年跻身ACM-ICPC World Finals以及百度Astar总决赛
昵称navi和navimoe
★李津羽
浙江大学2011级计算机系博士生
在浙大CAD&CG实验室从事科研工作
精彩书摘
2.5.5 最小生成树
给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,那么这棵树就叫做生成树(Spanning Tree)。如果边上有权值,那么使得边权和最小的生成树叫做最小生成树(MST,Minimum Spanning Tree)。
例如我们假设有这样一个图:把顶点看作村庄,边看作计划要修建的道路。为了在所有的村庄间通行,恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费,那么求解使得道路建设费用最小的生成树就是最小生成树问题。
常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然,生成树是否存在和图是否连通是等价的,因此我们假定图是连通的。
1.最小生成树问题1(PrIm算法)
首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似,都是从某个顶点出发,不断添加边的算法。
首先,我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边,并把它加到T中。不断进行这个操作,就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。
Comments