acl_cpp.maxflow

maxflow.mf_graph

# mf_graph<ll>
from acl_cpp.maxflow import mf_graph

This is a library to solve the maximum flow problem.

Constructor

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

Creates a graph with \(n\) vertices and \(0\) edges.

Constraints

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

Complexity

\(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

Adds an edge from vertex \(\mathit{from\_}\) to vertex \(\mathit{to}\) with maximum capacity \(\mathit{cap}\) and flow \(0\). Returns the index of the added edge (0-origin).

Constraints

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

Complexity

Amortized \(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) Equivalent to flow(s, t, (1 << 63) - 1).
(2) Sends as much flow as possible from vertex \(s\) to vertex \(t\) up to the flow limit \(\mathit{flow\_limit}\), and returns the amount of flow sent.
flow can be called multiple times. For detailed behavior, see the Appendix.

Constraints

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

Complexity

Let \(m\) be the number of edges added.

\(O((n + m) \sqrt{m})\) (when all edge capacities are \(1\))
\(O(n^2 m)\)
Let \(F\) be the return value, \(O(F(n + m))\)
Reference: Dinic’s algorithm and its complexity

mf_graph.min_cut

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

Returns a bool array cut of length \(n\) as defined below.

cut[i] indicates whether vertex \(i\) is reachable from vertex \(s\) in the current residual graph.

Calling min_cut(s) after calling flow(s, t) exactly once will return the minimum cut between \(s\) and \(t\). For detailed behavior, see the Appendix.

mf_graph.edge

This is a class representing an edge in the mf_graph. It consists of read-only variables from_, to, cap, and flow.
cap represents the maximum capacity, and flow represents the current flow.
from is a reserved word, so it is named from_.

Constructor

# 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

Returns the current state of the \(i\)-th added edge.

Constraints

Let \(m\) be the number of edges added so far.

\(0 \le i < m\)

Complexity

\(O(1)\)

mf_graph.edges

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

Returns the current state of all edges. The edges are ordered by the order they were added.

Complexity

\(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

Changes the maximum capacity of the \(i\)-th (0-origin) added edge to \(\mathit{new\_cap}\) and the flow to \(\mathit{new\_flow}\). For details, see the Appendix.

Constraints

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

Examples

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())