NgLib::MaxFlowGraph(Cap)

$n$ 頂点 $0$ 辺のグラフを作ります。

n = 10
graph = MaxFlowGraph(Int64).new(n)

$0$ 頂点 $0$ 辺のグラフを作ります。

graph = MaxFlowGraph(Int64).new

頂点 from から頂点 to へ最大容量 cap、流量 $0$ の辺を追加します。

何番目に追加された辺であるかを返します。

n = 10
graph = MaxFlowGraph(Int64).new(n)
graph.add_edge(0, 1, 1) # => 0
graph.add_edge(1, 3, 2) # => 1
graph.add_edge(5, 6, 8) # => 2

$i$ 番目に変更された辺の容量、流量をそれぞれ new_cap, new_flow に変更します。

他の辺の容量、流量は変更しません。

今の内部の辺の状態を返します。

辺の順番は add_edge での追加順と同じです。

頂点 $s$ から頂点 $t$ へ流せるだけ流し、流せた量を返します。

複数回呼ぶことも可能ですが、同じ結果を返すわけではありません。 挙動については以下を参考にしてください。

• https://atcoder.github.io/ac-library/document_ja/appendix.html

n = 4
graph = MaxFlowGraph(Int64).new(n)
graph.add_edge(0, 1, 10) # => 0
graph.add_edge(1, 2, 2)  # => 1
graph.add_edge(0, 2, 5)  # => 2
graph.add_edge(1, 3, 6)  # => 3
graph.add_edge(2, 3, 3)  # => 4

graph.flow(0, 3, 6)   # => 6
graph.flow(0, 3, 100) # => 9  (本来の挙動であれば 3 を返します。)

ameba:disable Metrics/CyclomaticComplexity

頂点 $s$ から頂点 $t$ へ流せるだけ流し、流せた量を返します。

複数回呼ぶことも可能ですが、同じ結果を返すわけではありません。 挙動については以下を参考にしてください。

• https://atcoder.github.io/ac-library/document_ja/appendix.html

n = 4
graph = MaxFlowGraph(Int64).new(n)
graph.add_edge(0, 1, 10) # => 0
graph.add_edge(1, 2, 2)  # => 1
graph.add_edge(0, 2, 5)  # => 2
graph.add_edge(1, 3, 6)  # => 3
graph.add_edge(2, 3, 3)  # => 4

graph.flow(0, 3) # => 9

今の内部の辺の状態を返します。

辺の順番は add_edge での追加順と同じです。

長さ $n$ の配列を返します。 $i$ 番目の要素には、頂点 $s$ から $i$ へ残余グラフで到達可能なとき、またその時のみ true を返します。

flow(s, t) を flow_limit なしでちょうど一回呼んだ後に呼ぶと、 返り値は $s, t$ 間の mincut に対応します。