✅ARC074D
F - Lotus Leaves diff: 2208
考えたこと
最小カットがらみであることは既知
グラフが与えられて頂点SからTまで到達できないようにするためにいくつの頂点を取り除けば良いかを答える問題
取り除くのが「頂点」ではなく「辺」なら素直な最小カットの問題
ということは頂点を辺に変換すればいい
新しく導入した赤い辺だけを重み1にし、他の辺を重み無限にする。最小カットを求めれば赤い辺を最小の本数切断する。
それ以外の辺は切られない程度に太くすれば良い
到達不能にできないのはSとTが並んでる時、それ以外は最悪全ての頂点を取り除けば到達不能にできる
1 MLE
ライブラリの実装が悪いか、使い方が悪いか
最悪20000頂点、10000頂点から199本の辺がでる
行と列の頂点を追加すれば+200頂点で、各頂点から出るのは2本になるが…
メモリ食いすぎるのはハッシュテーブルがメモリ食いなせいだよな…
AC
20万辺は厳しそうだったのと、最小カット勉強会で試してみて頂点数が増えることの影響はあまり大きくなさそうだったので、頂点数を増やして辺を削減することにした
各頂点から「縦または横に並んでる頂点」に直接辺を張るのではなく「縦頂点」「横頂点」を介してつながるようにした
これで最悪200万本だったのが3万本まで減る
pydef solve(H, W, world):
CHAR_S, CHAR_T, CHAR_O = b"STo"
leaf = set()
for pos in world.allPosition():
if world.mapdata[pos] == CHAR_S:
start = pos
if world.mapdata[pos] == CHAR_T:
goal = pos
if world.mapdata[pos] == CHAR_O:
leaf.add(pos)
sy, sx = divmod(start, W)
gy, gx = divmod(goal, W)
if sy == gy or sx == gx:
return -1
INF = 10000
d = Dinic(H * W * 2 + H + W)
O_BG = H * W
O_Y = H * W * 2
O_X = H * W * 2 + H
for pos in leaf:
pos2 = pos + O_BG
d.add_edge(pos, pos2, 1)
y, x = divmod(pos, W)
d.add_edge(pos2, y + O_Y, INF)
d.add_edge(pos2, x + O_X, INF)
d.add_edge(y + O_Y, pos, INF)
d.add_edge(x + O_X, pos, INF)
d.add_edge(start, sy + O_Y, INF)
d.add_edge(start, sx + O_X, INF)
d.add_edge(gy + O_Y, goal, INF)
d.add_edge(gx + O_X, goal, INF)
ret = d.max_flow(start, goal)
return retRelated Pages
- →dp×重み付き区間スケジューリング問題×連立1次方程式×最小カット×最大独立集合問題×二部グラフの最大マッチング×dilworthの定理×区間スケジューリング×貪欲法×区間スケジューリング問題×マトロイド×マトロイド交差×有向全域木×カラフル全域木×指数時間アルゴリズム入門→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]