ABC193 F- Zebraness
フローを理解するためのいい問題だった
解法
こういうある状況と２種類の操作が与えられるので，どっちかに振り分けて最適にする感じの奴はmaxflowにだいたい帰着できる（多分）
詳しくはこれに色々書いた
この問題における状況はこんな感じに整理できる
操作P:マスを以下の盤面と対応するマスの色で塗る
操作Q:マスをこの盤面と対応するマスの色でない方の色で塗る
WBWBWBWBWBWBWBWB....
BWBWBWBWBWBWBWBW....
WBWBWBWBWBWBWBWB....
BWBWBWBWBWBWBWBW....
WBWBWBWBWBWBWBWB....
BWBWBWBWBWBWBWBW....
この2つの操作で割り当てるのを考えると，最小カット問題に帰着できそうである．
最小カットはコストを最小化する問題であるので，一見値を最大化したいこの問題にうまく適用できないように思うかもしれないが，元々それぞれ隣り合う頂点間に辺が張られていて，そこからカットする辺の本数をできるだけ少なくする問題だと思うと結局最小カットで解けるのが分かるだろう．よって最初にans=2*n*(n-1)としておいて，そこから後で最小カットを引いてやれば良い．
すると，各グリッドの隣り合う頂点間（u→v）のコストは以下のように定義できる．
・頂点uが操作Pで塗られた場合，頂点vが操作Pで塗られていたらコスト0，操作Qで塗られていたらコスト1だけかかる
・頂点uが操作Qで塗られた場合，頂点vが操作Pで塗られていたらコスト1，操作Qで塗られていたらコスト0だけかかる
要するに異なる操作によって塗られていればそれを消すコストとして1が，同じ操作によって塗られていればそれは消す必要がないのでコスト0というふうにすれば良い．
また，今は「塗る」というその頂点に何も色が定義されていない前提であったが，もちろん元々黒の頂点を白で塗ることはできない．よって，以下をさらに定義する．
・頂点uの元の色が操作Pで塗られた時と色が一致する場合，操作Pで塗ったときはコスト0が，一致しない場合はコストINFがかかる
・頂点uの元の色が操作Qで塗られたときと色が一致する場合，操作Pで塗ったときはコストINFが，操作Qで塗ったときはコスト0がかかる
要するに，一致していれば元々その色で塗られていたのだからコスト0，そうでなければそれは違法なので莫大なコストがかかる，とすればいい．
あとは上記の関係性に従って，上の記事のチートシートに従い，辺を張って流せばよい．
