Livedoorブログからの移動
はてなブログからの移動

Save your cats | Aizu Online Judge

解き方

  • pileを頂点、fenceを辺としたグラフを考えると、その双対グラフの最小全域木（コストは、fenceの長さ）を求めれば良い
  • 双対グラフを求めるためには、最短閉路の列挙などする必要があり面倒
  • 元の平面グラフの全域木に使われた辺を、双対グラフ上で削除すると、そのグラフは双対グラフの全域木となる
    • もとのグラフで最大全域木を求めて、辺全体のコストから引けば、双対グラフの最小全域木のコストが求められる

ハマったところ

  • 双対グラフの最小全域木を考える必要があることはわかったが、双対グラフの性質を存在ごと完全に忘れていた
    • 双対グラフの性質はまとめて覚えておく必要がありそう

github.com