Problem E: School Excursion

Tetsuya Shiota

問題概要

• 修学旅行でｇ個のクラスがある場所から有る場所へ移動したい。
• n個の駅があり、m個の電車の運行情報がある
• 電車は必ずi番目の駅からi+1番目の駅に向かう(1<=i < m)
• 複数のクラスが同時刻に同じ駅に到着することができない
• 最終駅には最大何クラス到着できるか。
• それを実現するときの最小コストはいくらか。

​

サンプル１

駅１

駅２

時間

１

２

２

３

３

１０

５

２０

１０

１０

０

0

サンプル１

駅１

駅２

時間

１

２

２

３

３

１０

５

２０

１０

９

１

5

サンプル１

駅１

駅２

時間

１

２

２

３

３

１０

５

２０

１０

８

２

15

サンプル１

時間

進行方向

駅１

駅２

２

３

１

サンプル１

時間

進行方向

駅１

駅２

２

３

１

capacity ∞

capacity 1

capacity 1

サンプル１

時間

進行方向

駅１

駅２

２

３

１

capacity ∞

capacity 1

capacity 1

到着する時間のみに注目

サンプル１

到着時間

進行方向

駅１

駅２

２

３

０

capacity ∞

capacity 1

capacity 1

サンプル２

時間

１

２

３

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

５

４

１００

２

３

１０

０

０

cost 0

サンプル２

時間

１

２

３

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

５

４

１００

２

３

８

２

０

cost 9

サンプル２

時間

１

２

３

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

５

４

１００

２

３

８

1

1

cost 11

サンプル２

時間

１

２

３

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

０

１

３

１０

１２

２

１１

５

４

１００

２

３

８

0

2

cost 111

サンプル２

到着時間

進行方向

０

３

１２

２

１１

駅１

駅2

駅3

∞

解法

最小費用流

計算量

ノード数

2*n*m

エッジ数

n * m * m + n * m

最大流用

g

最小費用流 O(C*E * lg V)

よって、g * n * (m + m^2) * lg (2*n*m) *

10 * 100 * 420 * lg(4000) ≒　500万(データセット２０個）

結果

First Accept

​

hogloid 100min

関連問題

最小費用流 重みマッチング

AOJ 2293 Dangerous Tower

​

最大流最大マッチング

AOJ 2168 Luigi's Tavern

元ネタ

なし。

最小費用流の問題を本番で解きたくてしかたないのに、結局今まで本番で解けなくて悔しくて最小費用流に思いを馳せてたら思いついた。