haar_lib/flow/
mod.rs

1//! フロー問題
2
3pub mod dinic;
4pub mod ford_fulkerson;
5
6pub mod min_cost_flow;
7
8/// 最大フロー問題を扱うトレイト。
9pub trait MaxFlow {
10    /// 容量の型
11    type Cap;
12    /// 頂点数`n`の空のグラフを返す。
13    fn new(n: usize) -> Self;
14    /// 頂点`u`から頂点`v`へ容量`cap`の辺を張る。
15    fn add_edge(&mut self, u: usize, v: usize, cap: Self::Cap);
16    /// 頂点`s`から頂点`t`への最大フローを求める。
17    fn max_flow(&mut self, s: usize, t: usize) -> Self::Cap;
18    /// 最大フローを達成するのに通った辺を返す。
19    fn get_edges(&self, i: usize) -> Vec<(usize, Self::Cap)>;
20    /// フローを初期化する。
21    fn reset(&mut self);
22}
haar_lib/flow/mod.rs

haar_lib/flow/
mod.rs
