AOJ2224: Save your cats
Save your cats | Aizu Online Judge
解き方
- pileを頂点、fenceを辺としたグラフを考えると、その双対グラフの最小全域木（コストは、fenceの長さ）を求めれば良い
- 双対グラフを求めるためには、最短閉路の列挙などする必要があり面倒
- 元の平面グラフの全域木に使われた辺を、双対グラフ上で削除すると、そのグラフは双対グラフの全域木となる
- もとのグラフで最大全域木を求めて、辺全体のコストから引けば、双対グラフの最小全域木のコストが求められる
ハマったところ
- 双対グラフの最小全域木を考える必要があることはわかったが、双対グラフの性質を存在ごと完全に忘れていた
- 双対グラフの性質はまとめて覚えておく必要がありそう
