競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2224 Save your cats

薔薇園の魔女に比べたら11454倍楽

解法

閉路を含まなくするためにできるだけ少ない長さの辺を削りたい.
すなわち,できるだけ辺の総和が長くなるように閉路を含まないグラフを作りたい
よって最大全域森を作ればよい.

これはクラスカル法で最小全域木の作り方と同じように貪欲に長い辺から使って構成していけば作成可能.