acl_cpp.maxflow

maxflow.mf_graph

# mf_graph<ll>
from acl_cpp.maxflow import mf_graph

最大フロー問題を解くライブラリです。

コンストラクタ

# mf_graph::mf_graph(int n)
def mf_graph(n: int = 0) -> mf_graph

\(n\) 頂点 \(0\) 辺のグラフを作ります。

制約

\(0 \le n < 2^{31}\)

計算量

\(O(n)\)

mf_graph.add_edge

# int mf_graph::add_edge(int from, int to, ll cap)
def mf_graph.add_edge(from_: int, to: int, cap: int) -> int

頂点 \(\mathit{from\_}\) から頂点 \(\mathit{to}\) へ最大容量 \(\mathit{cap}\) 流量 \(0\) の辺を追加します。何番目に追加された辺かを返します (0-origin) 。

制約

\(0 \le \mathit{from\_} < n\)
\(0 \le \mathit{to} < n\)
\(0 \le \mathit{cap} < 2^{63}\)

計算量

ならし \(O(1)\)

mf_graph.flow

# (1) ll mf_graph::flow(int s, int t)
def mf_graph.flow(s: int, t: int) -> int

# (2) ll mf_graph::flow(int s, int t, ll flow_limit)
def mf_graph.flow(s: int, t: int, flow_limit: int) -> int

(1) flow(s, t, (1 << 63) - 1) と等価です。
(2) 頂点 \(s\) から頂点 \(t\) へ流量 \(\mathit{flow\_limit}\) に達するまで流せる限り流し、流せた量を返します。
複数回呼ぶことも可能です。詳細な挙動は Appendix を参照してください。

制約

\(0 \le s < n\)
\(0 \le t < n\)
\(s \neq t\)
\(0 \le \mathit{flow\_limit} < 2^{63}\)

計算量

\(m\) を追加された辺数として

\(O((n + m) \sqrt{m})\) (辺の容量がすべて \(1\) のとき)
\(O(n^2 m)\)
返り値を \(F\) として \(O(F(n + m))\)
参考文献: Dinic 法とその計算量

mf_graph.min_cut

# vector<bool> mf_graph::min_cut(int s)
def mf_graph.min_cut(s: int) -> list[bool]

以下で定める長さ \(n\) の bool の配列 cut を返します。

cut[i] は、現在の残余グラフにおいて、頂点 \(s\) から頂点 \(i\) へ到達可能かどうか

flow(s, t) をちょうど \(1\) 回呼んだ後に min_cut(s) を呼ぶと、返り値は \(s\)-\(t\) 間の最小カットに対応します。詳細な挙動は Appendix を参照してください。

mf_graph.edge

mf_graph 上の辺を表す class です。read-only な変数 from_, to, cap, flow からなります。
cap は最大容量、flow は現在の流量を表します。
from は予約語なので from_ としています。

コンストラクタ

# mf_graph::edge::edge(int from, int to, ll cap, ll flow)
def mf_graph.edge(from_: int, to: int, cap: int, flow: int) -> mf_graph.edge

mf_graph.get_edge

# mf_graph::edge mf_graph::get_edge(int i)
def mf_graph.get_edge(i: int) -> mf_graph.edge

\(i\) 番目に追加された辺の現在の状態を返します。

制約

\(m\) をこれまでに追加された辺の数として

\(0 \le i < m\)

計算量

\(O(1)\)

mf_graph.edges

# vector<mf_graph::edge> mf_graph::edges()
def mf_graph.edges() -> list[mf_graph.edge]

すべての辺の現在の状態を返します。辺は追加された順に並びます。

計算量

\(O(m)\)

mf_graph.change_edge

# void mf_graph::change_edge(int i, ll new_cap, ll new_flow)
def mf_graph.change_edge(i: int, new_cap: int, new_flow: int) -> None

\(i\) 番目 (0-origin) に追加された辺の最大容量を \(\mathit{new\_cap}\) 、流量を \(\mathit{new\_flow}\) に変更します。詳細は Appendix を参照してください。

制約

\(0 \le i < m\)
\(0 \le \mathit{new\_flow} \le \mathit{new\_cap} < 2^{63}\)

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_d

from acl_cpp.maxflow import mf_graph
HASH = ord('#')
DOT = ord('.')

N, M = map(int, input().split())
grid = [bytearray(input().encode()) for _ in range(N)]

s = N * M
t = s + 1
g = mf_graph(N * M + 2)

# s -> even / odd -> t
for i in range(N):
    for j in range(M):
        if grid[i][j] == HASH:
            continue
        v = i * M + j
        if (i + j) % 2 == 0:
            g.add_edge(s, v, 1)
        else:
            g.add_edge(v, t, 1)

# even -> odd
for i in range(N):
    for j in range(M):
        if (i + j) % 2 or grid[i][j] == HASH:
            continue
        v0 = i * M + j
        if i > 0 and grid[i - 1][j] == DOT:
            g.add_edge(v0, v0 - M, 1)
        if i + 1 < N and grid[i + 1][j] == DOT:
            g.add_edge(v0, v0 + M, 1)
        if j > 0 and grid[i][j - 1] == DOT:
            g.add_edge(v0, v0 - 1, 1)
        if j + 1 < M and grid[i][j + 1] == DOT:
            g.add_edge(v0, v0 + 1, 1)

print(g.flow(s, t))

for e in g.edges():
    if e.from_ == s or e.to == t or e.flow == 0:
        continue
    i0, j0 = divmod(e.from_, M)
    i1, j1 = divmod(e.to, M)
    
    if i0 + 1 == i1:
        grid[i0][j0] = ord('v')
        grid[i1][j1] = ord('^')
    elif i1 + 1 == i0:
        grid[i1][j1] = ord('v')
        grid[i0][j0] = ord('^')
    elif j0 + 1 == j1:
        grid[i0][j0] = ord('>')
        grid[i1][j1] = ord('<')
    else:
        grid[i1][j1] = ord('>')
        grid[i0][j0] = ord('<')

for row in grid:
    print(row.decode())