✅ABC193F

F - Zebraness

• 整理
  • 2色で塗り分け→グラフのカット
    • グラフのカットとはグラフの頂点集合を二つの集合に分けたもののこと
    • つまり2色での塗り分けとグラフのカットは本質的に同じもの
  • 最大カット→二部グラフなら片側を反転
    • グラフの最小カットは最大流で解ける
    • しかしこの問題は[最大カット]
    • グラフがグリッドグラフなので、二部グラフ
    • 二部グラフの片側の頂点の塗りを反転すれば、すべての辺について「同じ色か異なる色か」が反転する
    • これで「色が違っていれば+1」が「色が同じならば+1」に変わる
    • 色が違ってる辺を最小にする、つまり最小カット
  • 

---

from ABC193 ABC193F F - Zebraness

• 考えたこと
  • 横幅が最大100
    • 2^100はメモリに持てないので上からDPするのはダメそう
  • 2色で塗るので二部グラフになる？
    • 隣が同じ色になるしかない時もある
  • グリーディな解法がある？
    • サンプルは通ったが提出したら20WA、やっぱダメか
  • 連結したハテナの塊ごとに2種類の市松模様のどちらかを選ぶ？
    • 2個以上の連結成分を最悪2500個作れるので2^2500は無理
    • それぞれは独立に計算できるか…
    • タイムアウト
• 公式解説
  • Project Selection Problemに帰着して最大流
    • 知識としては知ってたのに全く思いつかなかったなぁ…
• 改めて考察
  • まず「グラフの頂点を白黒2色に塗り分ける」という設定を「グラフのカットについて考える」と理解すべきだった
    • グラフのカットとはグラフの頂点集合を二つの集合に分けたもののこと
  • カットだと理解した上で「最小カットなら最大流で解ける」と連想がつながる
  • 今回は「グラフの隣り合う頂点の色が異なっていれば+1」
    • 色が異なってる(カットエッジである)ことをプラスに評価している
    • これでは最大カット問題になる、一般的にはNP完全
  • グリッドグラフが二部グラフであることを利用
    • 「二部グラフの片側の頂点の色を反転」する
    • すると、すべての辺の「頂点の色が異なっているか」が反転する
    • これで「隣り合う頂点の色が異なっていれば-1」にできる
    • グリッドグラフの場合、要するに市松模様の頂点を反転するということ
• 実装
  • N=1の時に0を返す
  • Dinicの実装自体にバグがあった
    • グラフに孤立点があると頂点数を間違えて配列を必要な量より小さくしてしまう
    • 頂点数を明示的に渡すようにした
  • AC py

def solve(N, world):
    if N == 1:
        return 0

    d = Dinic(N * N + 2)
    for u, v in world.allEdges():
        d.add_edge(u, v, 1, True)

    start = N * N
    goal = start + 1
    for pos in world.allPosition():
        x, y = divmod(pos, N)
        if world.mapdata[pos] != CHAR_Q:
            p1 = (world.mapdata[pos] == CHAR_B)
            p2 = ((x + y) % 2 == 0)
            if p1 ^ p2:
                d.add_edge(start, pos, 100)
            else:
                d.add_edge(pos, goal, 100)

    f = d.max_flow(start, goal)
    return (2 * N * (N - 1)) - f