ABC205 F Grid and Tokens
この問題は次のような問題に帰着することができる.
「$ N個の駒と, $ H種類の食べ物と$ W種類の飲み物がある. 各駒は$ A_i \leq a \leq C_iを満たす食べ物$ aと, $ B_i \leq b \leq D_iを満たす飲み物$ bが好みである. 各食べ物・飲み物は1個の駒にしか割り当てることができない. このとき, 食べ物と飲み物の両方が割り当てられた駒の数の最大値を求めよ.」
この問題は, 最大流問題となっている. 具体的には, 次のようなグラフ上で最大流問題を解けばよい.
頂点は食べ物, 飲み物に加え, 駒を2セット, 始点$ sと終点$ tを用意する.
$ sから各食べ物に対して辺を張る. また, 各飲み物から$ tに対して辺を張る. さらに, 各食べ物からその食べ物を好む1セット目の駒に対して, 2セット目の駒からその駒が好む各飲み物に対して辺を張る. また, 1セット目の駒から2セット目の駒へ, 対応する駒に辺を張る.
流量はすべて$ 1とする.
よって最大流を求める適切なアルゴリズムを用いることで, この問題を解くことができた.