bipartite_matching.hpp ファイル

#include "../../kyopro_library/template.hpp"
#include "../../kyopro_library/graph/flow/max_flow.hpp"

[ソースコード]

クラス
struct	BiInfo
	二部グラフのパラメータ [詳解]

関数
vector< pair< int, int > >	BipartiteMatching (const vector< vector< int > > &g)
	二部グラフの最大マッチングを返す
BiInfo	GetBiInfo (const vector< vector< int > > &g)
	二部グラフのパラメータを求める

関数詳解

BipartiteMatching()

vector< pair< int, int > > BipartiteMatching

(

const vector< vector< int > > &

g

)

二部グラフの最大マッチングを返す

覚え書き

O(E*sqrt(V))

注意

G は二部グラフであること

bipartite_matching.hpp の 7 行目に定義があります。

参照先 MaxFlow::add_edge(), MaxFlow::flow(), MaxFlow::MaxFlow().

GetBiInfo()

BiInfo GetBiInfo

(

const vector< vector< int > > &

g

)

二部グラフのパラメータを求める

覚え書き

O(E*sqrt(V))

注意

G は二部グラフであること

bipartite_matching.hpp の 42 行目に定義があります。

参照先 BiInfo::max_independent_set, BiInfo::max_matching, BiInfo::min_edge_cover, BiInfo::min_vertex_cover.