PAT 解题报告 1018. Public Bike Management (30)

题目描述:

给一张图, 每个node都代表一个杭州的一个借或者还自行车站点, node上的值表示当前这个站点拥有多少量自行车, 每条边表示两个站点之间要花多少时间从一个站点到另一个站点, 给定一个有问题的站点, 求出从控制中心(PBMC)到该站点的最短路径并且使得带出去以及拿回来的自行车的数量最少.

算法分析:

可以这么做: (1)用最短路径算法(比如迪杰斯特拉)得到从PBMC到问题站点的所有最短路径(2)DFS枚举每一天最短路径, 找到那条带回来的自行车和送出去的自行车数量同时最小的那天最短路径.

注意点:

这个题目其实有点坑, 知道算法可能还要注意一下两点才能AC:

(1) 从PBMC到问题站点, 只能在这个顺序上进行每个站点车辆数量的调整, 在从问题站点返回PBMC的时候不能调整路径上的站点, 所以这个就导致有可能从PBMC送出去车辆也有可能带回来车辆(直觉上好像不太合理, 既然要带回来, 那么从出去的时候干嘛不少送一点呢?但是没办法, 这个题目似乎就是这么要求的)

(2) 从哪些最短路径总选择调整的车辆的数量最小的那条时, 题目总的描述非常模糊以及容易误导, 题目中是这么说的:“If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.”, 我一开始理解成了只要比较送出去的车辆的数量就行了, 其实测试数据才不是这么测试的呢, 其实应该按照“首先选择send最少的,send相同时选择take back最少的。“这条标准从所有的最短路径中选择 (第七个case应该就是卡在这里).

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on May 1, 2013