ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

最小全域木(クラスカル法)

AOJ 2511 - 沈みゆく島

問題 提出コード 解法 まずは前から見ていき、移動経路が確保できなくなるタイミングを探します。 そして、その直前からさかのぼって行き、今構築済みの木に最小限の辺を足して、全域木になるようにしていけばよいです。 基本的には最小全域木と同じ考え方で…

ABC065 D - Built?

問題 提出コード 解法 考察でごり押したら最小全域木とかいうやつを使っていたみたいです。 初期状態だと辺の可能性が約本あるので、これだと何をするにも不便です。 ですが、実は本程度まで減らすことができます。 個の座標をxについてソートした場合の隣り…