AOJ 2293 - Dangerous Tower - ツバサの備忘録

問題
 提出コード

解法

$A_{i},B_{i}$ 全て含めて、横の長さと箱が1:1に対応します。
なので、横の長さと箱をマッチングさせていくことを考えます。
箱 $i$ について、

$A_{i}$ とマッチングさせる
$B_{i}$ とマッチングさせる
マッチングさせない

という3つの選択肢が存在します。

それぞれの場合について、高さがどれだけ増えるか、ということを考えると、

$A_{i}$ とマッチングさせる
→ $B_{i}$ 増加
$B_{i}$ とマッチングさせる
→ $A_{i}$ 増加
マッチングさせない
→増加なし

となります。
これを、コストに置き換えます。
はじめ、 $A_{i} + B_{i}$ だけポイントを貰っていたとすると、それぞれの選択によるコストは、

$A_{i}$ とマッチングさせる
→ $A_{i}$ のコストがかかる
$B_{i}$ とマッチングさせる
→ $B_{i}$ のコストがかかる
マッチングさせない
→ $A_{i} + B_{i}$ のコストがかかる

となります。
あとは、それぞれの箱をマッチングさせ、最小コストになるようにすればよいです。
これを求めるのに最小費用流を用います。
超頂点 $s,t$ 、箱を表す $N$ 個の頂点、横の長さを表す頂点を用意します(横の長さを表す頂点は、 $A_{i},B_{i}$ の種類が個数になります)。
$s$ から箱の頂点それぞれにコスト0の辺を張る
箱の頂点から、 $A_{i}$ を表す頂点にコスト $A_{i}$ の辺を張る
箱の頂点から、 $B_{i}$ を表す頂点にコスト $B_{i}$ の辺を張る
箱の頂点から、 $t$ にコスト $A_{i} + B_{i}$ の辺を張る
横の長さを表す頂点から、 $t$ にコスト0の辺を張る
という操作を行います。容量は全て1です。
あとは、 $s$ から $t$ に、 $N$ だけフローを流すときの最小コストを求めれば、
$\sum (A_{i} + B_{i})$ から引くことで答えが求まります。

感想

これと似ているな、と思って解いたので初めてマッチング問題を自力で解けました。いいですね。