drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ yukicoder 木 木DP Greedy 木上の最大マッチング問題 葉から考える 最大安定集合・最小点被覆・最小辺被覆 最大安定集合問題 グラフ NP困難(特殊構造なので解ける) 最適化の考察：変形しても悪化しない けんちょん本演習問題 【問題集】DPのステップアップ 【問題集】木DPの入門 そのまま覚えたいシンプル設定の中堅以上の典型問題 いわゆる「木上の最大安定集合問題」です！ 超典型問題です。 問題へのリンク 問題概要 頂点数 の木が与えられます。木からいくつかの頂点を選んで削除します。その結果、木はいくつかの連結成分に分かれます。 分かれた連結成分の個数の最大値を求めてください。 制約 最大安定集合問題 さて、今回の問題は、実は「木上の最大安定集合問題」に一致します。 安定集合とは、グラフの頂点集合の部分集合であって「どの 2 頂点も隣接しない」という条件を満たすものをいいます。最大安定集合問題は、最大サイズの安定集合を求める問題です。 最大安定集合問題は一般には NP 困難であり、解決は困難です。しかしたとえば二部グラフ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2021%2F08%2F06%2F104900" title="yukicoder No.763 Noelちゃんと木遊び - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2021-08-06 10:49:00 rich https://drken1215.hatenablog.com/entry/2021/08/06/104900 1.0 100%