posts - 43,  comments - 9,  trackbacks - 0
500pt
50个点的地图,从0开始按照顺序访问一系列点(不超过50个),访问顺序给出,一个点可能访问多次。某些点停着若干辆汽车。可以走路,也可以开车。开车的速度比走路快。但是限定一辆汽车只能使用一次,也就是下车后这辆车就作废。问按要求访问完所有点的最短总耗时。 先floyd求每对点之间走路时间和开车时间。对于访问顺序中的每一步,使用每辆车都有个节省的时间。这就相当于建个二分图,左边x是访问顺序中的每一步,右边y是每一辆车。xi与yj的边权就是第i步使用第j辆车能节省的时间。 最后结果就是总的走路时间减去最大权匹配。

[floyd最短路 二分图最大权匹配]
posted on 2011-05-12 11:22 wolf5x 阅读(272) 评论(0)  编辑 收藏 引用 所属分类: topcoder

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


<2011年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

随笔分类(59)

随笔档案(43)

cows

搜索

  •  

最新评论

评论排行榜