けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

ラグランジュ緩和

CS Academy 082 DIV1 E - Water Supply

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