5

如果您有一个国家/地区的完整巴士时刻表，您如何找出 1 天内两个指定站点之间可载客的最大人数？

我假设巴士时刻表为您提供每个巴士站的出发和到达时间的完整列表以及每辆巴士的容量。您在问题中得到了开始和结束。

您可以确定一系列公共汽车，以最短的时间到达目的地，并填满从一开始沿着这条路径离开的所有公共汽车，然后当每辆公共汽车到达一个站点时，只需将尽可能多的乘客转移到下一个站点离开的巴士。然而，这没有理由应该具有最大容量。

这个问题最快可以解决什么？例如，假设对于 M 个城市，我总共有 N 条记录；路线记录 Rᵢ 包含号码 Kᵢ、容量 Cᵢ，以及 Kᵢ 城市号码、Kᵢ 到达时间和 Kᵢ 出发时间的列表。（Rᵢ 中的第一个到达时间和最后一个离开时间无关。）广度优先搜索程序可以在 O(M*N) 时间内解决这个问题吗？

4

1 回答 1

3

这不是一个奇怪的谜题。这是一个算法问题。解决这个问题的一种方法是为每个（位置，到达时间）和（位置，出发时间）制作一个有向图。每个到达节点对同一位置的所有不早于的出发点都有无限容量弧。每个出发节点都有一条到每个适当到达节点的弧线（根据公共汽车时刻表），并根据公共汽车的容量加权。然后你可以使用你最喜欢的算法来找到从你的源到你的接收器的最大流量。

您的源节点应该是您开始位置的零时间到达节点，您的汇节点应该是您结束位置的结束时间的出发节点。

于 2013-07-08T21:56:56.677 回答