✅ABC193F

https://gyazo.com/e9f159c0e0b9070204a70e715eb1c8bd

整理

グラフの最小カットは最大流で解ける

二部グラフの片側の頂点の塗りを反転すれば、すべての辺について「同じ色か異なる色か」が反転する

これで「色が違っていれば+1」が「色が同じならば+1」に変わる

色が違ってる辺を最小にする、つまり最小カット

https://gyazo.com/eb51702b0e1c427719cdfb3c2ff4b3f9

----

ABC193F

https://gyazo.com/e9f159c0e0b9070204a70e715eb1c8bd

考えたこと

横幅が最大100

2^100はメモリに持てないので上からDPするのはダメそう

2色で塗るので二部グラフになる？

隣が同じ色になるしかない時もある

グリーディな解法がある？

サンプルは通ったが提出したら20WA、やっぱダメか

連結したハテナの塊ごとに2種類の市松模様のどちらかを選ぶ？

2個以上の連結成分を最悪2500個作れるので2^2500は無理

それぞれは独立に計算できるか…

タイムアウト

公式解説

知識としては知ってたのに全く思いつかなかったなぁ…

改めて考察

まず「グラフの頂点を白黒2色に塗り分ける」という設定を「グラフのカットについて考える」と理解すべきだった

グラフのカットとはグラフの頂点集合を二つの集合に分けたもののこと

カットだと理解した上で「最小カットなら最大流で解ける」と連想がつながる

今回は「グラフの隣り合う頂点の色が異なっていれば+1」

色が異なってる(カットエッジである)ことをプラスに評価している

これでは最大カット問題になる、一般的にはNP完全

グリッドグラフが二部グラフであることを利用

「二部グラフの片側の頂点の色を反転」する

すると、すべての辺の「頂点の色が異なっているか」が反転する

これで「隣り合う頂点の色が異なっていれば-1」にできる

グリッドグラフの場合、要するに市松模様の頂点を反転するということ

実装

N=1の時に0を返す

Dinicの実装自体にバグがあった

グラフに孤立点があると頂点数を間違えて配列を必要な量より小さくしてしまう

頂点数を明示的に渡すようにした

AC

code: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)

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