2021-08-06から1日間の記事一覧
yukicoder
木
木DP
Greedy
木上の最大マッチング問題
葉から考える
最大安定集合・最小点被覆・最小辺被覆
最大安定集合問題
グラフ
NP困難(特殊構造なので解ける)
最適化テク:解を変形していく(最適性を失わずに)
けんちょん本演習問題
【問題集】DPのステップアップ
【問題集】木DPの入門
そのまま覚えたいシンプル設定の中堅以上の典型問題
いわゆる「木上の最大安定集合問題」です! 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてくだ…