UAPC2011 問題D

問題

各部屋は通路でつながっている。
2つの勢力があり、各部屋をそれぞれの勢力に割り振り、それぞれの勢力の部屋同士が通路でつながっていないようにしたい。(両勢力は少なくとも1つの部屋を所持する)
しかし、部屋の数と通路はすでに建設中で、通路を壊すことでしか対応できない。しかし通路を壊すにはコストがかかる。

部屋の数と通路の情報が与えられるので、これを実現する最小コストを求める。

考え方

最小カット。
与えられる通路は有向グラフだけど、別勢力が来れる状態っていうのは結局ダメなので、無向グラフで考えても一緒になる。
コストが負もありえるが、負のコストは取ればとるほどコストが低くなるので、すべて取らなければいけない。そのうえで、まだ条件を満たせない場合は、最小カットを求め、負のコストの和を加えたものが答えになる。

最小カットは、Spaghetti Sourceさん( http://www.prefield.com/algorithm/ )の無向グラフの全域最小カットを使わせてもらった。
もし(s,t)-最大流を使う場合は、ある1点からその点以外のすべての頂点への最大流(＝最小カット)を求めた最小値が答えになると思われるけど、計算量が大きくなる、、、