haar_lib/flow/
mod.rs

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

haar_lib/flow/
mod.rs
