問題はこちら
問題概要
枚のカードがグリッド上に並んでおり,にあるカードにはが書かれている.行からいくつか選び,選んだカードの上に赤いトークンを置く.列からいくつか選び,選んだカードの上に青いトークンを置く.その後,トークンが置かれているカードに書かれた整数の和が得点となる.ただし,赤いトークンと青いトークンがともに置かれているカードであって,書かれている整数が負であるものが存在する場合,得点はとなる.得点としてあり得る最大値を求めよ.
解説
行または列を選ぶと点を得ます.これを「行を選ぶと点を得る」,「列を選ぶと点を得る」,「行と列をともに選ぶと点を失う」と考えることにすると,選択間にコストがかかる問題となり,Project Selection Problem(燃やす埋める問題)と同じく最小カットを求める問題に帰着させることができます.選択間にかかるコストを表にしてみます.
の場合,このままだと上手くグラフを作れないので行の選択の順番を変更してみます.ちなみに,選択間のコストは行と列の間にしかかからないためこの変更を行うことができます.
の場合も同様にして以下のコストがかかることが分かります.
グラフの構築
ここからは実際にグラフを構築していきます.最小カットに対応させるため,行/列に対応する頂点および始点・終点を用意します.行を選ぶことと頂点を側集合に含めることに対応させ,列を選ぶことと頂点を側集合に含めることに対応させると- 行を選ぶと点を得る 行に対応する頂点を側集合に含めるとコストがかかる.
- 列を選ぶと点を得る 列に対応する頂点を側集合に含めるとコストがかかる.
- 行と列をともに選ぶと点を失う 行に対応する頂点を側集合に,列に対応する頂点を側集合に含めるとコストが (の場合)かかる.
となるため,これをもとにグラフが構築できます.
このグラフの最小カットが答えとなります.
また,およびが負の場合は以下の記事の様に負辺除去をすれば良いです.
頂点数は,辺数はであるので計算量で解くことができます.
Project Selection Problem(燃やす埋める問題)に関する基礎知識は以下の記事を参考にしてください.
kanpurin.hatenablog.com
Project Selection Problem(燃やす埋める問題)の他の問題は以下にまとめているので参考にしてください.
kanpurin.hatenablog.com