燃やす埋める練習問題２ - かんプリンの学習記録

燃やす埋める(Project Selection Problem)の練習問題についての解説です。

ポイント
問題概要
解説
提出プログラム
感想

ポイント

最大化を最小化へ言い換える
グラフ表現可能なコストの性質
2部グラフの性質を用いたの選択肢の順序変更

問題概要

頂点数 ${|L|,|R|}$ 、辺数 ${M}$ の二部グラフおよび各頂点の重み ${w_{L_i},w_{R_i}}$ が与えられます。 ${j}$ 番目の辺は頂点 ${L_{x_j}}$ と頂点 ${R_{y_j}}$ を結んでいます。このグラフにおける最大重み独立集合を求め、重みの和を出力してください。

最大重み独立集合とは独立集合のうち、頂点の重みの和が最大となるもののことです。

${1 \leq |L|,|R| \leq 100}$
${0 \leq M \leq L\times R}$
${1\leq w_{L_i},w_{R_i} \leq 10^9}$
${1\leq x_j\leq L}$
${1\leq y_j\leq R}$
${i\neq j \Leftrightarrow (x_i,y_i)\neq (x_j,y_j)}$

解説

燃やす埋める問題に関する基礎知識は以下の記事を参考にしてください．
kanpurin.hatenablog.com

各頂点を独立集合として[選ばない/選ぶ]を選択します。頂点 ${L_i}$ を選ぶ際のコストは以下のようになります。[選ぶ]と ${w_{L_{i}}}$ の利得が発生するので ${-w_{L_{i}}}$ のコストがかかると考えます。これは頂点 ${R_i}$ を選んだ際も同様です。

各辺 ${(L_{x_j},R_{y_j})}$ について、頂点 ${L_{x_j}}$ と頂点 ${R_{y_j}}$ をともに[選ぶ]ことはできないのでともに[選ぶ]を選択すると ${\infty}$ のコストが発生するようにします。

このままだとうまくグラフを作ることができないので二部グラフの性質を利用します。頂点 ${L_i}$ の選択肢の順番を入れ替えると以下のようにグラフで表せるコストの形になりました。二部グラフであることから、 ${L}$ と ${R}$ を結ぶ辺しかなく、全てのコストがこの形で書けることが分かります。

負の辺( ${-w_{L_{i}},-w_{R_{i}}}$ )が存在するため、あらかじめ ${-w_{L_{i}},-w_{R_{i}}}$ を加算しておくことで、[選ばない]を選択した際に ${w_{L_{i}},w_{R_{i}}}$ がかかると考えることができます。
以上をまとめるとコストは以下のようになります。

この最小コストが最小カットとなるようなグラフが構築でき、例えば入力例2では以下のようなグラフが構築できます。 ${L_i}$ を[選ぶ]ときは ${S}$ 側の集合に、[選ばない]ときは ${T}$ 側の集合に割り当てることを意味し、 ${R_i}$ を[選ぶ]ときは ${T}$ 側の集合に、[選ばない]ときは ${S}$ 側の集合に割り当てることを意味します。このときの ${S}$ 側の頂点から ${T}$ 側の頂点に向かう辺の重みの和がカットのコストとなります(この辺の話は他の資料が詳しいです)。