acl_cpp.mincostflow

mincostflow.mcf_graph

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

最小費用流問題を扱うライブラリです。

コンストラクタ

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

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

制約

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

計算量

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

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

制約

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

計算量

ならし \(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) flow(s, t, (1 << 63) - 1) と等価です。
(2) 流量 \(\mathit{flow\_limit}\) に達するか、これ以上流せなくなるまで頂点 \(s\) から頂点 \(t\) へ流し、流せた量と、その量を流すための最小コストを返します。

制約

slope と同じ

計算量

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) slope(s, t, (1 << 63) - 1) と等価です。

(2) 流量に対する最小コストは広義単調増加・下に凸な折れ線 (区分線形関数) となります。この折れ線の頂点を返します。

具体的には、流量 \(x\) の時の最小コストを \(g(x)\) として、\((x, g(x))\) の列を以下の条件を満たすように返します。

返り値の最初の点は \((0, 0)\)
返り値の \(x\) は狭義単調増加、\(g(x)\) は広義単調増加
返り値の最後の点は、y = flow(s, t, flow_limit)[0] として \((y, g(y))\)
返り値の中間の点で \(g(x)\) の傾きが増加する（すなわち、同一直線上の \(3\) 点を含まない）
返り値の点を順に繋いだ折れ線が \(g(x)\ (0 \le x \le \text{flow_limit})\) のグラフを表現する

\(g(x)\) が 64 bit 符号付き整数 に収まらない場合、mod \(2^{64}\) で等しい値を返すはずです。

制約

\(s \neq t\)
\(0 \leq s, t \lt n\)
slope や flow を合わせて複数回呼んだときの動作は未定義
辺のコストの最大値を \(x\) として、\(n \cdot x \leq 8 \times 10^{18} + 1000\)
- より正確には、(単純パスの最大コスト) \(\leq 8 \times 10^{18} + 1000\)
- これが満たされない場合の動作は未定義

計算量

\(F\) を流量、\(m\) を追加した辺の本数として

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

mcf_graph.edge

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

コンストラクタ

# 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

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

制約

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

\(0 \le i < m\)

計算量

\(O(1)\)

mcf_graph.edges

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

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

計算量

\(O(m)\)

使用例

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