F - Grid and Tokens - AtCoder Beginner Contest 205
フローの張り方が分からなかった。
------------------------------------------------------
問題
H*Wのグリッドがある
N個のコマで、i番目のコマについて
・指定された長方形領域のどこかに一つ置く
・置かない
のいずれかを選択できる。
ここで同じ列、行に二つ以上のコマを置けないとして
最大で何個のコマを置けるか。
------------------------------------------------------
制約
1<=H, W, N <= 100
--------------------------------------------
解法
複数の選択について相互に制約が生まれる場合は大抵フローな気がする、実際この問題はそうで
行と列を頂点として扱うと上手くいく。
そうするとイメージ的には、行hと列wを繋ぐ辺を選ぶと(h, w)にコマを置いたという様な感じだ。
行列を頂点として扱うのはLotus Leavesでもそうだったので典型かもしれない。
具体的には以下のように辺を貼ればいい（辺の流量はすべて1）
赤く囲った部分は1,2行目と2,3,4列目について
コマを置けるという事を意味する
