CPLib.MaxFlow
Defined in cp-library@0.5.3
最大フロー問題、最小カット問題
Values
namespace CPLib.MaxFlow::Dinic
bfs
Type: [c : CPLib.MaxFlow::CapacityLike] CPLib.MaxFlow::MaxFlowGraph c -> CPLib.MaxFlow::MaxFlowGraph c
残余グラフ上でBFSしてレベルを更新する
dfs
Type: [c : CPLib.MaxFlow::CapacityLike] Std::I64 -> c -> CPLib.MaxFlow::MaxFlowGraph c -> (CPLib.MaxFlow::MaxFlowGraph c, c)
開始地点からの最短経路DAG（levelから得られる）においてDFSして経路を一つ発見し、フロー・残余グラフを更新する。
更新された残余グラフと、新たに流されたフローの量を返す。
一度調べた辺を次のdfsで調べないよう、iterを更新する。
Parameters
v: 現在の頂点f: 流してよいフローの量
reset_iter
Type: CPLib.MaxFlow::MaxFlowGraph c -> CPLib.MaxFlow::MaxFlowGraph c
iterをすべて0にリセットする。
reset_level
Type: CPLib.MaxFlow::MaxFlowGraph c -> CPLib.MaxFlow::MaxFlowGraph c
levelをすべて-1にリセットする。
solve
Type: [c : CPLib.MaxFlow::CapacityLike] CPLib.MaxFlow::MaxFlowGraph c -> (CPLib.MaxFlow::MaxFlowGraph c, c)
最大フローを求める
namespace CPLib.MaxFlow::MaxFlowGraph
add_edge
Type: [c : CPLib.MaxFlow::CapacityLike] Std::I64 -> Std::I64 -> c -> CPLib.MaxFlow::MaxFlowGraph c -> CPLib.MaxFlow::MaxFlowGraph c
グラフに辺を追加する
追加された辺の識別子を返す。
Parameters
graph: グラフfrom: 始点の頂点番号to: 終点の頂点番号cap: 辺の容量
add_edge_id
Type: [c : CPLib.MaxFlow::CapacityLike] Std::I64 -> Std::I64 -> c -> CPLib.MaxFlow::MaxFlowGraph c -> (CPLib.MaxFlow::MaxFlowGraph c, CPLib.Graph::EdgeId)
グラフに辺を追加する（辺IDを返す）
追加された辺の識別子を返す。
Parameters
graph: グラフfrom: 始点の頂点番号to: 終点の頂点番号cap: 辺の容量
create
Type: Std::I64 -> Std::I64 -> Std::I64 -> CPLib.MaxFlow::MaxFlowGraph c
グラフを作成する
Parameters
n: 頂点数s: 開始頂点番号t: 終了頂点番号
get_flow
Type: [c : CPLib.MaxFlow::CapacityLike] CPLib.Graph::EdgeId -> CPLib.MaxFlow::MaxFlowGraph c -> c
ある辺に流れているフローを取得する
Parameters
eid:add_edgeで得た辺の識別子graph: グラフ
get_min_cut
Type: [c : CPLib.MaxFlow::CapacityLike] CPLib.MaxFlow::MaxFlowGraph c -> Std::Array Std::Bool
最小カットを取得する
先にmaximize_flowを呼び出しておく必要がある。
sから到達可能な頂点をtrue、到達不可能な頂点をfalseとする配列を返す。
注：最小カットにおいて除去される辺の容量の和はmaximize_flowで得られたフローの量に等しい。
Parameters
graph: グラフ
maximize_flow
Type: [c : CPLib.MaxFlow::CapacityLike] CPLib.MaxFlow::MaxFlowGraph c -> (CPLib.MaxFlow::MaxFlowGraph c, c)
最大フローを計算する
残余グラフと流されたフローの量を返す。
Parameters
graph: グラフ
Types and aliases
namespace CPLib.MaxFlow
MaxFlowGraph
Defined as: type MaxFlowGraph c = unbox struct { ...fields... }
最大フロー問題のグラフの型
型パラメータcは容量の型です。
field graph
Type: CPLib.Graph::Graph (c, Std::I64, c)
グラフ。(現在の容量, 逆辺のインデックス, 初期容量)
field s
Type: Std::I64
開始地点
field t
Type: Std::I64
終了地点
field level
Type: Std::Array Std::I64
レベル。残余グラフ上での開始地点から任意の地点への距離。到達できない場合は-1。
field iter
Type: Std::Array Std::I64
DFSにおいて次に調べる辺のインデックス
field queue
Type: Std::Option (RingBuffer::RingBuffer Std::I64)
BFSで用いるキュー