yukicoder No.957 植林 - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

${H}$ 行 ${W}$ 列のマスのうちいくつかを選ぶ. ${i}$ 行 ${j}$ 列のマスを選ぶと, ${G_{i,j}}$ 円失う. また, ${i}$ 行目のすべてのマスを選ぶと ${R_i}$ 円得ることができ, ${j}$ 列目のすべてのマスを選ぶと ${C_j}$ 円得ることができる. このとき最大何円得ることができるか.

${1\leq H,W\leq 300\\ 0\leq G_{i,j},R_i,C_j\leq 10^9}$

解説

マスを選ぶのではなく, 行や列を選びその行や列にあるマスをすべて選ぶようにする
( ${(i,j)}$ を選んだ時, ${i}$ 行も ${j}$ 列も使わないなら ${(i,j)}$ を選ぶ必要がないため)

${\downarrow}$

以下の条件で利得の最大化を行うことになる.

${i}$ 行目を選ぶと, ${R_i-\sum_{j=1}^{W}G_{i,j}}$ 円を得る.
${j}$ 列目を選ぶと, ${C_j-\sum_{i=1}^{H}G_{i,j}}$ 円を得る.
ただし, ${i}$ 行目と ${j}$ 列目のどちらも選ぶと上に加えて ${G_{i,j}}$ 円を得る.

${\downarrow}$

選ぶ/選ばないという選択と, 複数の選択の間に対する制約(罰則条件)があるのでProjectSelectionProblem(俗にいう燃やす埋める問題)を解くアルゴリズムを使えそう.
ProjectSelectionProblemについてはこちら

上の条件はすべて利得になっているのでProjectSelectionProblemに対応させるため損失に書き直す.

${i}$ 行目を選ぶと, ${\sum_{j=1}^{W}G_{i,j}-R_i}$ 円を失う.
${j}$ 列目を選ぶと, ${\sum_{i=1}^{H}G_{i,j}-C_j}$ 円を失う.
ただし, ${i}$ 行目と ${j}$ 列目のどちらも選ぶと上に加えて ${-G_{i,j}}$ 円を失う.

しかしこれだと3つ目の条件のコストが負になるのでうまくいかない.

${\downarrow}$

まず行を選ぶ. その後列を選ぶとき, その列のまだ選んでないマスのコストだけ追加でコストがかかる, と考えると条件は以下のように変更できる.

${i}$ 行目を選ぶと, ${R_i-\sum_{j=1}^{W}G_{i,j}}$ 円を得る.
${j}$ 列目を選ぶと, ${C_j}$ 円を得る.
ただし, ${j}$ 列目を選んで ${i}$ 行目を選んでいないときは ${G_{i,j}}$ 円を失う.

先ほどと同様に条件を変更すると

${i}$ 行目を選ぶと, ${\sum_{j=1}^{W}G_{i,j}-R_i}$ 円を失う.
${j}$ 列目を選ぶと, ${-C_j}$ 円を失う.
ただし, ${j}$ 列目を選んで ${i}$ 行目を選んでいないときは ${G_{i,j}}$ 円を失う.

これをグラフで表すと以下のようになる. 赤の頂点が行を表し, 青の頂点が列を表す.

まだ負のコストがあるので全体に ${R_i,C_j}$ を足すことで以下のように変更する.

このグラフのsからtまで流すときの最小カットを ${M}$ とすると
答えは ${-(M-\sum_{i=1}^{H}R_i-\sum_{j=1}^{W}C_j)}$ となる.(さっき足した分を引いている.)
頂点数は ${O(H+W)}$ , 辺数は ${O(HW)}$ となり間に合う.
また, sから ${j}$ に向かう辺のコストは0なので辺を張る必要はない.