随笔 - 11, 文章 - 0, 评论 - 12, 引用 - 0
数据加载中……

POJ 1639 Picnic Planning 最小限度生成树

这是我有史以来写得最长的一个程序,前段时间就看了这个题,在网上搜了一下算法,当时看得还有点不太明白,大牛也都说这题代码太长
不好写,开始写了一些,后面发现不会写了,就放下了。昨天又来看这个题,居然写出来了,不过还是花了我一个晚上的时间来调试,开始
交一次结果就RE了,后来在网上找来了官方数据一个一个的运行才发现找圈DFS的时候陷入了死循环,加了一个标志变量,还是WA,后来
反复看解思路才知道换边的时候每一次循环最多只能换一次,而且要换差值最大的那条边,又加了一个优先队列,才终于攻下这道题。

题目大意是:
矮人虽小却喜欢乘坐巨大的轿车,轿车大到可以装下无论多少矮人。某天,N(N≤5000)个矮人打算到野外聚餐。为了集中到聚餐地点,矮人A要么开车到矮人B家中,留下自己的轿车在矮人B家,然后乘坐B的轿车同行;要么直接开车到聚餐地点,并将车停放在聚餐地。
虽然矮人的家很大,可以停放无数量轿车,但是聚餐地点却最多只能停放K辆轿车。现在给你一张加权无向图,它描述了N个矮人的家和聚餐地点,要你求出所有矮人开车的最短总路程。

    [输入文件]
第一行是整数M(M<=49000),接下来M行描述了M条道路。每行形式如同:S1 S2 x,S1和S2均是大于0小于5000的整数,x小于等于1000。最后一行包含两个整数k,root。root表示聚餐的地点。

    [输出文件]
仅一行,形式如同:Total miles driven: xxxXxx是整数,表示最短总路程。

解题思路:

  1)将根节点从图中去除掉
  2)对去除根节点的图求MST,注意这里去除根后的图可能是不连通的,所以计算MST的时候要对每个连通图都进行计算
这里我选择用Kruscal算法+并查集求MST.求完后用DFS将属于同一个连通分量的点放在一个数组里面,并得到连通分量的个数。
  3)针对每一个连通分量,选择从根节点到这个连通分量里的节点的具有最小权值的边加入图中,假设有deep个连通分
量则一共需要加deep条边
  4)由1)2)3)步骤即得到一棵deep最小限度生成树
  5)假设题目限定的停车位数是k,那么还需要找k - deep条从根节点出发的边,所以循环k- deep次,每次做
如下操作:
      a)假设对于节点k, 边[root, j, w]不在当前树中(权值为w), 那么如果把这条边加入树中就会构成一条环
      b)假设这个环中不是与根直接相连的具有最大权值的边为[from, to, weight]
    遍历寻找具有最大weight - w值的边,如果这个差值大于0,则将这条边[root, j]加入树中并去除边[from, to],如果差值小于等于0则退出


以下是我的代码:

posted on 2010-05-04 21:12 acleast 阅读(2419) 评论(8)  编辑 收藏 引用

评论

# re: POJ 1639 Picnic Planning 最小限度生成树  回复  更多评论   

orz 神牛。。求数据或数据地址
2010-05-13 11:57 | sedreaming

# re: POJ 1639 Picnic Planning 最小限度生成树  回复  更多评论   

@sedreaming
你只要google East Central North America 2000就可以了
2010-05-13 14:56 | acleast

# re: POJ 1639 Picnic Planning 最小限度生成树  回复  更多评论   

@acleast
虽然没有找到....不过终于把这题ac了...再次膜拜神牛
2010-05-14 12:21 | sedreaming

# re: POJ 1639 Picnic Planning 最小限度生成树[未登录]  回复  更多评论   

@sedreaming
过了就行,其实我很菜
2010-05-14 16:40 | acleast

# re: POJ 1639 Picnic Planning 最小限度生成树[未登录]  回复  更多评论   

orz神牛,,orz
2011-02-17 16:00 | waaihun

# re: POJ 1639 Picnic Planning 最小限度生成树[未登录]  回复  更多评论   

第5步
遍历寻找具有最大weight - w值的边,如果这个差值大于0,则将这条边[root, j]加入树中并去除边[from, to],如果差值小于等于0则退出

当除边[from,to]时,不需要更新data数据吗?
2011-03-01 22:38 | 初学者

# re: POJ 1639 Picnic Planning 最小限度生成树  回复  更多评论   

@初学者
不用啊,我有用dd数组来标志
2011-03-01 22:42 | acleast

# re: POJ 1639 Picnic Planning 最小限度生成树[未登录]  回复  更多评论   

请问官方数据在哪?
2011-06-30 16:30 | 123

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