AlienDP
グラフ
グラフの辺数を削減する
最小全域木
ラグランジュ緩和
密グラフ
二分探索
N個からK個を選ぶ設定の問題
CSAcademy
全域木を考える
個人的要復習
制約条件:グラフの次数列
NP困難(特殊構造なので解ける)
高度典型
マルチテストケース問題
AlienDP
グラフの辺数削減テク:ある最適解に含まれ得る辺以外を削除する
ラグランジュ緩和か、、、 しかしこれ、ある特定の 1 頂点について次数が 以下であるような最小全域木を求める問題とみなせるわけだけど、こんなんが解けるのは面白い。 全域最小木スライドにある通り、全頂点について次数が 以下となるような最小全域木を求…