Struct contest_algorithms::graph::flow::FlowGraph

pub struct FlowGraph {
    pub graph: Graph,
    pub cap: Vec<i64>,
    pub cost: Vec<i64>,
}

Representation of a network flow problem with (optional) costs.

Fields

graph: Graph

Owned graph, managed by this FlowGraph object.

cap: Vec<i64>

Edge capacities.

cost: Vec<i64>

Edge cost per unit flow.

Implementations

impl FlowGraph

pub fn new(vmax: usize, emax_hint: usize) -> Self

Initializes an flow network with vmax vertices and no edges.

pub fn add_edge(&mut self, u: usize, v: usize, cap: i64, rcap: i64, cost: i64)

Adds an edge with specified directional capacities and cost per unit of flow. If only forward flow is allowed, rcap should be zero.

pub fn dinic(&self, s: usize, t: usize) -> (i64, Vec<i64>)

Dinic's algorithm to find the maximum flow from s to t where s != t. Generalizes the Hopcroft-Karp maximum bipartite matching algorithm. V^2E in general, min(V^(2/3),sqrt(E))E when all edges are unit capacity, sqrt(V)E when all vertices are unit capacity as in bipartite graphs.

Panics

Panics if the maximum flow is 2^63 or larger.

pub fn min_cut(&self, dist: &[i64]) -> Vec<usize>

After running maximum flow, use this to recover the dual minimum cut.

pub fn mcf(&self, s: usize, t: usize) -> (i64, i64, Vec<i64>)

Among all s-t maximum flows, finds one with minimum cost, assuming s != t and no negative-cost cycles.

Panics

Panics if the flow or cost overflow a 64-bit signed integer.