n個からk個選んだものの最適化

AtCoder ABC 116 D - Various Sushi (400 点)

学び多き問題。僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！問題へのリンク問題概要個の寿司があって、それぞれネタと美味しさをもっている。この中から個の寿司を選びたい。選んだ寿司集合のスコアは選んだ寿司の美…

ラグランジュ緩和か、、、なのんしかしこれ、ある特定の 1 頂点について次数が以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白いのんな。全域最小木スライドにある通り、全頂点について次数が以下となるような最…