ALPCの解説記事がなかったので書きます。書いていない問題についてはあとで追加します。
ALPC
AtCoder Library (ACL) のテストをするためのコンテストです。
https://atcoder.jp/contests/practice2/
D - Maxflow
問題文
$N$ 行 $M$ 列のマス目があります． 上から $i$ 行目，左から $j$ 番目のマス目をマス $(i,j)$ と呼ぶことにします．
現在，それぞれのマスは，障害物が置かれているか，空であるかのどちらかの状態です． これらの状態は，文字列 $S_1,S_2,\cdots,S_N$ にって表され， マス $(i,j)$ の状態は，$S_{i,j}=$
'#'なら障害物が置かれていること， $S_{i,j}=$'.'なら空であることを意味します．これらのマスに， $1\times2$ の大きさのタイルを置きたいです． タイルは，縦または横に連続する $2$ つの空マスの上に置くことができます． タイルを盤面からはみ出すように置くことや，障害物や他のタイルがすでに置かれているマスにタイルを重ねることは禁止されています． 最大でいくつのタイルを置くことができるか求めてください． また，実際にその最大値を達成する方法を $1$ つ示してください．
制約
- $1 \le N \le 100$
- $1 \le M \le 100$
- $S_i$ は
'#'と'.'のみからなる長さ $M$ の文字列
解説
マスを偶奇で分けて考えます。それぞれの空マス $(i,j)$ について、 $i+j$ が偶数になるマスを黒、奇数になるマスを白で塗ることにすると、市松模様になります。
ここに $1\times2$ の大きさのタイルを置くことは、黒マスと白マスをつなぐことと考えることができます。
すると、これは黒マスと白マスのペアを作ったとき、最大で何個ペアを作れるかという問題になります。つまり最大二部マッチング問題となり、maxflowを使って解くことができます。
- 黒マスと白マスをそれぞれ頂点とし、さらにソースとシンクの２つの頂点を追加します。
- ソースから全ての黒マスへの辺と、黒マスから隣り合う白マスへの辺と、全ての白マスからシンクへの辺を張ります。辺の容量は全て $1$ です。
- ソースからシンクへの最大流量を求めます。これが置けるタイルの個数です。
さらにこのときの各辺のフローを得る必要がありますが、これは ACL だと get_edge でできますので、よしなに。