CPLib.Bipartite
Defined in cp-library@0.15.2
二部グラフを扱うモジュール
計算量の n は頂点数(左右の合計)、m は辺数を表します。
Examples
// 左右に2頂点ずつある二部グラフ
let g = create(2, 2).add_edge(0, 0).add_edge(0, 1).add_edge(1, 1);
let flow = g.calc_flow;
// 最大マッチングは辺(0, 0)と辺(1, 1)
assert_eq(|_|"", flow.get_max_matching, [true, false, true])
Values
namespace CPLib.Bipartite::BipartiteGraph
@edges
Type: CPLib.Bipartite::BipartiteGraph -> Std::Array (Std::I64, Std::I64)
辺の配列を取得する
第i要素は、i番目に追加した辺の(左側の頂点番号, 右側の頂点番号)です。
計算量:O(1)
Parameters
graph: 二部グラフ
@left_size
Type: CPLib.Bipartite::BipartiteGraph -> Std::I64
左側の頂点数を取得する
計算量:O(1)
Parameters
graph: 二部グラフ
@right_size
Type: CPLib.Bipartite::BipartiteGraph -> Std::I64
右側の頂点数を取得する
計算量:O(1)
Parameters
graph: 二部グラフ
add_edge
Type: Std::I64 -> Std::I64 -> CPLib.Bipartite::BipartiteGraph -> CPLib.Bipartite::BipartiteGraph
二部グラフに辺を追加する
制約:0 <= left < left_size, 0 <= right < right_size
計算量:ならしO(1)
Parameters
left: 左側の頂点番号right: 右側の頂点番号graph: 二部グラフ
calc_flow
Type: CPLib.Bipartite::BipartiteGraph -> CPLib.Bipartite::BipartiteGraphFlow
二部グラフに対応する最大フロー問題を作成し、解く
計算量:O((n + m) sqrt(n))
create
Type: Std::I64 -> Std::I64 -> CPLib.Bipartite::BipartiteGraph
二部グラフを作成する
計算量:O(1)
Parameters
left_size: 左側の頂点数right_size: 右側の頂点数
maximize_flow
Deprecated: Use CPLib.Bipartite::BipartiteGraph::calc_flow instead.
Type: CPLib.Bipartite::BipartiteGraph -> CPLib.Bipartite::BipartiteGraphFlow
calc_flowの別名(非推奨)
namespace CPLib.Bipartite::BipartiteGraphFlow
calc_max_indep_set
Type: CPLib.Bipartite::BipartiteGraphFlow -> (Std::Array Std::Bool, Std::Array Std::Bool)
二部グラフの最大独立集合(最大安定集合)を取得する
計算量:O(n + m)
Returns
左側の頂点と右側の頂点のそれぞれについて、最大独立集合に含まれる頂点をtrue、含まれない頂点をfalseとするArray Boolを返す。
Parameters
max_flow: 二部グラフの最大フロー
calc_min_edge_cover
Type: CPLib.Bipartite::BipartiteGraphFlow -> Std::Array Std::Bool
二部グラフの最小辺カバーを取得する
制約:二部グラフに孤立点がない
計算量:O(n + m)
Returns
第i番目に追加した辺がカバーに含まれる場合はtrue、含まれない場合はfalseとする配列
Parameters
max_flow: 二部グラフの最大フロー
calc_min_vertex_cover
Type: CPLib.Bipartite::BipartiteGraphFlow -> (Std::Array Std::Bool, Std::Array Std::Bool)
二部グラフの最小点被覆を取得する
計算量:O(n + m)
Returns
左側の頂点の被覆と右側の頂点の被覆をそれぞれArray Boolとして返す。
ある頂点が被覆に含まれる場合はtrue、含まれない場合はfalseとなる配列が返される。
Parameters
max_flow: 二部グラフの最大フロー
get_max_indep_set
Deprecated: Use CPLib.Bipartite::BipartiteGraphFlow::calc_max_indep_set instead.
Type: CPLib.Bipartite::BipartiteGraphFlow -> (Std::Array Std::Bool, Std::Array Std::Bool)
calc_max_indep_setの別名(非推奨)
get_max_matching
Type: CPLib.Bipartite::BipartiteGraphFlow -> Std::Array Std::Bool
二部グラフの最大マッチングを取得する
計算量:O(m)
Returns
第i番目に追加した辺がマッチングに含まれる場合はtrue、含まれない場合はfalseとする配列
Parameters
max_flow: 二部グラフの最大フロー
get_min_edge_cover
Deprecated: Use CPLib.Bipartite::BipartiteGraphFlow::calc_min_edge_cover instead.
Type: CPLib.Bipartite::BipartiteGraphFlow -> Std::Array Std::Bool
calc_min_edge_coverの別名(非推奨)
get_min_vertex_cover
Deprecated: Use CPLib.Bipartite::BipartiteGraphFlow::calc_min_vertex_cover instead.
Type: CPLib.Bipartite::BipartiteGraphFlow -> (Std::Array Std::Bool, Std::Array Std::Bool)
calc_min_vertex_coverの別名(非推奨)
Types and aliases
namespace CPLib.Bipartite
BipartiteGraph
Defined as: type BipartiteGraph = unbox struct { ...fields... }
二部グラフの型
BipartiteGraphFlow
Defined as: type BipartiteGraphFlow = unbox struct { ...fields... }
二部グラフに対する最大フロー問題のグラフ