#atcoder #プログラミング #AHC045 # 町連結アルゴリズム

概要

問題の条件に、グループ内の町(2次元空間に散在)が道路で連結(全ての町に道路で到達できる)されていることというのがある。
グラフでよくある問題だと思うので最適アルゴリズムというのがあると思うが、一応自分で考え出したものを載せておく。
ちなみに、厳密には、その道路総長がより短い方が良い。
また、自分の場合は効果より安全を重視するので簡単を考慮している。

案1

直近を踏まえた一筆書き。

1. 全ての町で、直近の町を総当たりで求める。
2. その長さで町を降順ソートする。
3. ソート後を連結する。

案2

1. 案1の手順2まで行う。
2. 各町の有効状態を用意する。
3. 各町で次の処理をする。
   その町が直近になっている町を、その町のブランチ扱いとする。
   追加した町の有効状態を無効にする。
4. 各町で次の処理をする。
   ブランチ扱いの町を元の町と連結する。
   有効な町を一筆書きで連結する。

イメージ