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

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

グラフをツリーっぽくする

CS Academy 082 DIV1 E - Water Supply

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

AtCoder ARC 098 F - Donation (1000 点)

本番中に解きたかった... ARC 098 F Donation 問題概要 N 頂点 M 辺の連結な単純無向グラフがあります。 頂点 i には二つの整数 Ai, Bi が定められています。 このグラフ上で次のようなゲームをします。 初めに、W 円を持った状態で好きな頂点に立つ。 ただ…