500pt
50个点的地图，从0开始按照顺序访问一系列点（不超过50个），访问顺序给出，一个点可能访问多次。某些点停着若干辆汽车。可以走路，也可以开车。开车的速度比走路快。但是限定一辆汽车只能使用一次，也就是下车后这辆车就作废。问按要求访问完所有点的最短总耗时。
先floyd求每对点之间走路时间和开车时间。对于访问顺序中的每一步，使用每辆车都有个节省的时间。这就相当于建个二分图，左边x是访问顺序中的每一步，右边y是每一辆车。xi与yj的边权就是第i步使用第j辆车能节省的时间。
最后结果就是总的走路时间减去最大权匹配。
[floyd最短路 二分图最大权匹配]
posted on 2011-05-12 11:22
wolf5x 阅读(286)
评论(0) 编辑 收藏 引用 所属分类:
topcoder