No.009 D

※ コードは最後まで書ききれていない.

市は木構造になっているので, 各市ごとに全域木を作ればいい.

市にある町の数は最大で7なので, 道の数は最大で21である. それぞれの道を使う/使わないを全列挙し, 道の数が町の数-1となる組み合わせで幅優先探索を行って全域木を作れるかどうかを確認する.

こうして, 市ごとの全域木のコストの合計とその組み合わせの数を計算する. なお, 取り除く道のコストの合計より残す道のコストの合計の方が小さくなるので, 次のDPで有利になる.

次に市ごとに採用する全域木ごとの, 全体のコストとその組み合わせの数をDPで計算する.

ただし, 組み合わせの数は簡単にオーバーフローするので, 最初に残す道のコストを最大にしたときの整備コストを計算しておき, 以下は残す道のコストが最大のときからいくら減るかを指標にして小さい方から計算し, 組み合わせ数が $k$ を超えた場合は無限大扱いにしておく.