ARC056 C問題 部門分け
想定解だと思って書いた解法が、どうやらそうではなかったようなので書きます。
解法
最小カットを使います。
部門を分割することによって幾つかの絆が切られる事を考えると、ある部門を2つに分割するための最小コストは最小カットと等しくなります。
この「2つに分割するための最小コスト」が、部門を1つ増やすことによって得られるスコア K 以上であれば分割を行うとスコアが高くなることがわかります。
このように、部門を最小カットで分割することを繰り返すと最大スコアが得られます。
なお、部門の分割を最小カットで貪欲に切ると良いという証明はできていません。(実験をして大丈夫そうだったので書くと通ってしまいました)(証明は解説を頼ろうと思っていたら全然違う解法が書いてありました)
