旅行計画

Question

国の完全なバススケジュールをお持ちの場合、指定された2つの停留所間を1日で運ぶことができる最大人数はどのようにして知ることができますか？

私は、バスのスケジュールは、すべてのバス停留所の到着時間と各バスの容量の完全なリストを提供すると仮定します。あなたは質問の開始と終了のストップを与えられます。

目的地までの最短時間を与えるバスの列を決定し、この経路に沿って出発するすべてのバスを埋めることができます。その後、各バスが到着すると、数多くの乗客が離れる次のバスに可能です。しかし、これには最大容量が必要な理由はありません。

この問題が最も早く解決できるのは何ですか？たとえば、M都市では合計N件のレコードが与えられたとします。ルートレコードR numberは、番号Kᵢ、容量Cᵢ、およびKᵢ都市番号、Kᵢ到着時刻およびKᵢ出発時刻のリストを含む。 （R firstの最初の到着時間と最後の出発時間は無関係です）。幅優先探索プログラムはO（M * N）時間の質問を解決できますか？

Answer 1

これは奇妙なパズルではありません。それはアルゴリズムの質問です。これを解決する1つの方法は、すべて（位置、到着時間）および（位置、出発時間）ごとにノードを有する有向グラフを作成することである。各到着ノードは、同じ位置のすべての出発点に対して無期限の容量アークを有する。各出発ノードは、バスの容量で重み付けされた適切な到着ノード（バススケジュールごと）の弧を有する。次に、お気に入りのアルゴリズムを使用して、ソースからシンクまでの最大フローを見つけることができます。

あなたのソースノードは、開始位置に時間ゼロの到着ノードである必要があります。シンクノードは、終了位置の終了時刻に出発ノードにする必要があります。