https://kanpurin.hatenablog.com/entry/2022/08/28/201523

問題概要

${H\times W}$ 枚のカードがグリッド上に並んでおり， ${(i,j)}$ にあるカードには ${A_{i,j}}$ が書かれている． ${H}$ 行からいくつか選び，選んだカードの上に赤いトークンを置く． ${W}$ 列からいくつか選び，選んだカードの上に青いトークンを置く．その後，トークンが置かれているカードに書かれた整数の和が得点となる．ただし，赤いトークンと青いトークンがともに置かれているカードであって，書かれている整数が負であるものが存在する場合，得点は ${-10^{100}}$ となる．
得点としてあり得る最大値を求めよ．

${1\leq H,W\leq 100}$
${-10^9 \leq A_{i,j}\leq 10^9}$

解説

行 ${i}$ または列 ${j}$ を選ぶと ${A_{i,j}}$ 点を得ます．これを「行 ${i}$ を選ぶと ${A_{i,j}}$ 点を得る」，「列 ${j}$ を選ぶと ${A_{i,j}}$ 点を得る」，「行 ${i}$ と列 ${j}$ をともに選ぶと ${A_{i,j}}$ 点を失う」と考えることにすると，選択間にコストがかかる問題となり，Project Selection Problem(燃やす埋める問題)と同じく最小カットを求める問題に帰着させることができます．

選択間にかかるコストを表にしてみます．

${A_{i,j} > 0}$ の場合，このままだと上手くグラフを作れないので行の選択の順番を変更してみます．ちなみに，選択間のコストは行と列の間にしかかからないためこの変更を行うことができます．

${A_{i,j} < 0}$ の場合も同様にして以下のコストがかかることが分かります．

グラフの構築

ここからは実際にグラフを構築していきます．最小カットに対応させるため，行/列に対応する頂点および始点 ${S}$ ・終点 ${T}$ を用意します．行 ${i}$ を選ぶことと頂点を ${T}$ 側集合に含めることに対応させ，列 ${j}$ を選ぶことと頂点を ${S}$ 側集合に含めることに対応させると

行 ${i}$ を選ぶと ${A_{i,j}}$ 点を得る ${\longrightarrow}$ 行 ${i}$ に対応する頂点を ${S}$ 側集合に含めるとコストが ${-\sum_{i=1}^{W}A_{i,j}}$ かかる．
列 ${j}$ を選ぶと ${A_{i,j}}$ 点を得る ${\longrightarrow}$ 列 ${j}$ に対応する頂点を ${T}$ 側集合に含めるとコストが ${-\sum_{j=1}^{H}A_{i,j}}$ かかる．
行 ${i}$ と列 ${j}$ をともに選ぶと ${A_{i,j}}$ 点を失う ${\longrightarrow}$ 行 ${i}$ に対応する頂点を ${S}$ 側集合に，列 ${j}$ に対応する頂点を ${T}$ 側集合に含めるとコストが ${A_{i,j}}$ ( ${A_{i,j} < 0}$ の場合 ${\infty}$ )かかる．