from AtCoder Library Practice Contest ACLPC_D D - Maxflow 最大流 マスを市松模様に塗り分けると、タイルは必ず色の異なるマスを1つずつ踏む つまりタイルは二部グラフの辺であって、タイルの数を最大にするのは最大二部マッチング これは最大流に帰着できる