TopCoder SRM 695 (Div. 1) Medium. BearKRoads

解法

辺の両端のコスト和が大きいものを取ればだいたい最適だろう。

もうちょっと考えると、ある辺を取ったとき利益が減少する辺は高々 4 本ということも分かる。

そのため、上位 5K 本以外の辺を使うことはない。よって、${}_{5K}C_{K}≦6724520$ を全部試すことで解が得られる。

次数 3 以下に目が行き過ぎていて、K≦7 を見落としていた。注意力散漫。