Struct PrimalDual

Source

pub struct PrimalDual<'a> {
    graph: &'a BidirectionalSparseGraph,
    capacities: Vec<u64>,
    costs: Vec<i64>,
    potential: Vec<i64>,
    dist: Vec<i64>,
    prev_vertex: Vec<usize>,
    prev_edge: Vec<usize>,
    has_negedge: bool,
}

Fields§

§graph: &'a BidirectionalSparseGraph§capacities: Vec<u64>§costs: Vec<i64>§potential: Vec<i64>§dist: Vec<i64>§prev_vertex: Vec<usize>§prev_edge: Vec<usize>§has_negedge: bool

Implementations§

Source §

impl PrimalDual<'_>

Source

pub fn builder(vsize: usize, esize_expect: usize) -> PrimalDualBuilder

Source

fn bellman_ford(&mut self, s: usize)

Examples found in repository ?

crates/competitive/src/graph/minimum_cost_flow.rs (line 128)

124    pub fn minimum_cost_flow_limited(&mut self, s: usize, t: usize, limit: u64) -> (u64, i64) {
125        let mut flow = 0;
126        let mut cost = 0;
127        if self.has_negedge {
128            self.bellman_ford(s);
129        }
130        while flow < limit && self.dijkstra(s, t) {
131            for (p, d) in self.potential.iter_mut().zip(self.dist.iter()) {
132                *p = p.saturating_add(*d);
133            }
134            let mut f = limit - flow;
135            let mut v = t;
136            while v != s {
137                f = f.min(self.capacities[self.prev_edge[v]]);
138                v = self.prev_vertex[v];
139            }
140            flow += f;
141            cost += f as i64 * self.potential[t];
142            let mut v = t;
143            while v != s {
144                self.capacities[self.prev_edge[v]] -= f;
145                self.capacities[self.prev_edge[v] ^ 1] += f;
146                v = self.prev_vertex[v];
147            }
148        }
149        (flow, cost)
150    }

Source

fn dijkstra(&mut self, s: usize, t: usize) -> bool

Examples found in repository ?

crates/competitive/src/graph/minimum_cost_flow.rs (line 130)

124    pub fn minimum_cost_flow_limited(&mut self, s: usize, t: usize, limit: u64) -> (u64, i64) {
125        let mut flow = 0;
126        let mut cost = 0;
127        if self.has_negedge {
128            self.bellman_ford(s);
129        }
130        while flow < limit && self.dijkstra(s, t) {
131            for (p, d) in self.potential.iter_mut().zip(self.dist.iter()) {
132                *p = p.saturating_add(*d);
133            }
134            let mut f = limit - flow;
135            let mut v = t;
136            while v != s {
137                f = f.min(self.capacities[self.prev_edge[v]]);
138                v = self.prev_vertex[v];
139            }
140            flow += f;
141            cost += f as i64 * self.potential[t];
142            let mut v = t;
143            while v != s {
144                self.capacities[self.prev_edge[v]] -= f;
145                self.capacities[self.prev_edge[v] ^ 1] += f;
146                v = self.prev_vertex[v];
147            }
148        }
149        (flow, cost)
150    }

Source

pub fn minimum_cost_flow_limited( &mut self, s: usize, t: usize, limit: u64, ) -> (u64, i64)

Return (flow, cost).

Examples found in repository ?

crates/competitive/src/graph/minimum_cost_flow.rs (line 153)

152    pub fn minimum_cost_flow(&mut self, s: usize, t: usize) -> (u64, i64) {
153        self.minimum_cost_flow_limited(s, t, u64::MAX)
154    }

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_6_b.rs (line 14)

6pub fn grl_6_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, vs, es, f: u64, edges: [(usize, usize, u64, i64)]);
10    let mut builder = PrimalDualBuilder::new(vs, es);
11    builder.extend(edges.take(es));
12    let graph = builder.gen_graph();
13    let mut pd = builder.build(&graph);
14    let (flow, cost) = pd.minimum_cost_flow_limited(0, vs - 1, f);
15    writeln!(writer, "{}", if flow < f { -1 } else { cost }).ok();
16}