kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ グラフ 典型 解説 競技プログラミング 燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 最大化を最小化へ言い換える グラフ表現可能なコストの性質 2部グラフの性質を用いたの選択肢の順序変更 問題概要頂点数、辺数の二部グラフおよび各頂点の重みが与えられます。番目の辺は頂点と頂点を結んでいます。このグラフにおける最大重み独立集合を求め、重みの和を出力してください。最大重み独立集合とは独立集合のうち、頂点の重みの和が最大となるもののことです。 解説燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください． kan… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2022%2F08%2F05%2F065148" title="燃やす埋める練習問題２ - かんプリンの学習記録" 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-ak.f.st-hatena.com/images/fotolife/k/kanpurin/20220804/20220804011203.png Hatena Blog https://hatena.blog 2022-08-05 06:51:48 rich https://kanpurin.hatenablog.com/entry/2022/08/05/065148 1.0 100%