Coder Space

PKU 1639 Picnic Planning --- 度限制最小生成树

 

题意:给出若干个小矮人的家和一个公园,这些小矮人到公园去聚会,题中给了若干条路线,还有每条路线的长度,在这些路线上穿行需要开车,但是公园只可容纳一定数量的汽车,小矮人可以部分聚集到一起再一起开车到公园,求需要行驶的最短距离。 

思路:求最小生成树,其中某一个节点的度是限制的,即度限制最小生成树。 

解法:

(1)     由于公园的度是限制的,因此可以先忽略公园这个点,对其他的点求最小生成树,可能有多棵,即确切说应该是最小生成森林。

(2)     在每个连通分支中,选出到达公园最短的路,可知这些必定是最小限制生成树中的边,把这些边加到最小生成森林中,可得包括公园节点度为M的一棵最小生成树。

(3)     如果此时M>limit,则易知limit度限制树不存在。否则,公园节点的边从M增加到limit,每次做一次“差额最小添删操作”。即从公园节点V0添加一条到Vi的边,这样就形成一个环,然后删掉环里面最大的那条边(不与V0相连),差额为:cost(添加边) – cost(删除边)。枚举以V0为节点的未在生成树中的所有边,找出最小差额。如果差额大于0,即退出。否则,更新生成树权值:val = val + cost(添加边) – cost(删除边) 

注意:对于找最长边,可以先用DFS遍历生成树,记录每个节点viV0点的最长边长,和最长边的端点,需要O(n),然后每次以O(1)即可选出。进行一次添删边操作后,也需要O(n)时间维护。


源代码

posted on 2010-05-22 17:30 David Liu 阅读(371) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论