Struct BipartiteMatching

pub struct BipartiteMatching<F> { /* private fields */ }

最大フローによる最大二部マッチング

Implementations

impl<F: MaxFlow<Cap = u64>> BipartiteMatching<F>

pub fn new(left: usize, right: usize) -> Self

左側の頂点数がleft、右側の頂点数がrightの空の二部グラフを用意する。

pub fn add_edge(&mut self, i: usize, j: usize)

左側iと右側jに辺を張る。

pub fn matching(&mut self) -> u64

最大マッチングの辺数を返す。