beet's soil

競プロのことなど

AOJ 2511 沈みゆく島

キレた

新たに橋を掛けるという設定が完全にクソ
(最初に全部掛けてしまっていいんだからいらないだろ)

この問題は以下のように言い換えられる。

頂点を削除していく。元のグラフが初めて非連結になる時刻をTとする。(最後まで連結ならT=INF)
ここで、非連結かどうかは「沈んでいない頂点たちから誘導されるグラフ」において判定される。

以下の条件を満たす部分グラフの中で、辺の重みの総和が最小であるようなものを求めよ

  • 条件:任意の時刻 t (t < T) について、「沈んでいない頂点たちから誘導されるグラフ」が連結である
本質

読解