マスを二つに分類する最適化問題なので、最小カットで解けないかと思ってyosupoさんの記事で解ける条件を確認する。
「Xが赤で、Yが青ならZ円の報酬」
「Xが赤で、Yが赤ならZ円の罰金」
は最大カットになって解けないと思います。
この問題は異なる色に塗ると得になる制約なので、解けそうにない……と思ったが、市松模様の一方の色を反転すると、同じ色なら得になる制約に変換できる。
頂点なので一般のフローアルゴリズムで解けるのかわからなかったが、とりあえず書くと通った。
Dinicの計算量について
https://misawa.github.io/others/flow/dinic_time_complexity.html
