acl_cpp.mincostflow

mincostflow.mcf_graph

# mcf_graph<ll, ll>
from acl_cpp.mincostflow import mcf_graph

This is a library to solve the minimum cost flow problem.

Constructor

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

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

Constraints

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

Complexity

\(O(n)\)

mcf_graph.add_edge

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

Adds an edge from vertex \(\mathit{from\_}\) to vertex \(\mathit{to}\) with maximum capacity \(\mathit{cap}\), cost \(\mathit{cost}\), 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}, \mathit{cost} < 2^{63}\)

Complexity

Amortized \(O(1)\)

mcf_graph.flow

# (1) pair<ll, ll> mcf_graph::flow(int s, int t)
def mcf_graph.flow(s: int, t: int) -> tuple[int, int]

# (2) pair<ll, ll> mcf_graph::flow(int s, int t, ll flow_limit)
def mcf_graph.flow(s: int, t: int, flow_limit: int) -> tuple[int, int]

(1) Equivalent to flow(s, t, (1 << 63) - 1).
(2) Sends flow from vertex \(s\) to vertex \(t\) until the flow limit is reached or no more flow can be sent. Returns the amount of flow sent and the minimum cost to send that flow.

Constraints

Same as slope.

Complexity

Same as slope.

mcf_graph.slope

# (1) vector<pair<ll, ll>> mcf_graph::slope(int s, int t)
def mcf_graph.slope(s: int, t: int) -> list[tuple[int, int]]

# (2) vector<pair<ll, ll>> mcf_graph::slope(int s, int t, ll flow_limit)
def mcf_graph.slope(s: int, t: int, flow_limit: int) -> list[tuple[int, int]]

(1) Equivalent to slope(s, t, (1 << 63) - 1).

(2) The minimum cost for the flow is a polyline (piecewise linear function) that is non-decreasing and convex. Returns the vertices of this polyline.

Specifically, returns the sequence of \((x, g(x))\) such that \(g(x)\) is the minimum cost for flow \(x\), satisfying the following conditions:

The first point of the return value is \((0, 0)\).
\(x\) in the return value is strictly increasing, and \(g(x)\) is non-decreasing.
The last point of the return value is \((y, g(y))\), where y = flow(s, t, flow_limit)[0].
The slope of \(g(x)\) increases at the intermediate points of the return value (i.e., it does not contain three points on the same line).
The polyline connecting the points of the return value represents the graph of \(g(x)\ (0 \le x \le \text{flow_limit})\).

If \(g(x)\) does not fit in a 64-bit signed integer, it should return the value modulo \(2^{64}\).

Constraints

\(s \neq t\)
\(0 \leq s, t \lt n\)
Behavior is undefined when slope or flow are called multiple times together.
Let \(x\) be the maximum cost of an edge, then \(n \cdot x \leq 8 \times 10^{18} + 1000\).
- More precisely, (the maximum cost of a simple path)\({}\leq 8 \times 10^{18} + 1000\).
- Behavior is undefined if this is not satisfied.

Complexity

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

\(O(F (n + m) \log (n + m))\)

mcf_graph.edge

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

Constructor

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

mcf_graph.get_edge

# mcf_graph.edge mcf_graph::get_edge(int i)
def mcf_graph.get_edge(i: int) -> mcf_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)\)

mcf_graph.edges

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

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

Complexity

\(O(m)\)

Examples

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

from acl_cpp.mincostflow import mcf_graph

BIG = 10 ** 9
N, K = map(int, input().split())

# generate (s -> row -> column -> t) graph
# i-th row correspond to vertex i
# i-th col correspond to vertex n + i
g = mcf_graph(N * 2 + 2)
s = N * 2
t = N * 2 + 1

# we can "waste" the flow
g.add_edge(s, t, N * K, BIG)

for i in range(N):
    g.add_edge(s, i, K, 0)
    g.add_edge(N + i, t, K, 0)

for i in range(N):
    A = list(map(int, input().split()))
    for j, a in enumerate(A):
        g.add_edge(i, N + j, 1, BIG - a)

result = g.flow(s, t, N * K)
print(BIG * N * K - result[1])

grid = [bytearray(b'.' * N) for _ in range(N)]
for e in g.edges():
    if e.from_ == s or e.to == t or e.flow == 0:
        continue
    grid[e.from_][e.to - N] = ord('X')

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