らての精進日記

修行をします

aoj2224:Save your cats

解法

閉路をなくせばokです。閉路がないグラフ、つまり森を目指せばいいわけです。

グラフを森にするためにいくつかの辺を取り除くことになりますが、取り除く辺のコストの和を最小化したくなります。

取り除く辺の和を最小化する→残す辺のコストを最大化する、と言い換えることができます。
よって、グラフの全域森のなかで、辺のコストの合計が最も大きいものを求めたくなります。これは、クラスカル法をするときに、辺のコストが降順になるように辺をソートしておけばいいです。

ところでこの問題、平面グラフである必要はあるのでしょうか。
例えば、「重み付き無向グラフが与えられます。閉路をなくすために取り除く辺のコストを最小化しなさい」という問題の場合、グラフに平面性がある必要があるのでしょうか??

恐らく、猫を助けるという問題設定的に平面上のグラフを考えたくて、辺が交差すると意味不明になるので平面性を付けた、という感じだと思いますが、平面性についての理解がないので確信が持てず悲しい・・・


ちなみに下のコードは一年半くらい前に書いたコードです。本格的に競プロを初めて3カ月くらいのときですが、あのころより確実にコードが汚くなっているような気がします。

コード