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,
    queue: BinaryHeap<(Reverse<i64>, usize)>,
}

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§queue: BinaryHeap<(Reverse<i64>, usize)>

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 140)

136    pub fn minimum_cost_flow_limited(&mut self, s: usize, t: usize, limit: u64) -> (u64, i64) {
137        let mut flow = 0;
138        let mut cost = 0;
139        if self.has_negedge {
140            self.bellman_ford(s);
141        }
142        while flow < limit && self.dijkstra(s, t) {
143            let shortest = self.dist[t];
144            for (p, d) in self.potential.iter_mut().zip(self.dist.iter()) {
145                *p = p.saturating_add((*d).min(shortest));
146            }
147            let mut f = limit - flow;
148            let mut v = t;
149            while v != s {
150                f = f.min(self.capacities[self.prev_edge[v]]);
151                v = self.prev_vertex[v];
152            }
153            flow += f;
154            cost += f as i64 * (self.potential[t] - self.potential[s]);
155            let mut v = t;
156            while v != s {
157                self.capacities[self.prev_edge[v]] -= f;
158                self.capacities[self.prev_edge[v] ^ 1] += f;
159                v = self.prev_vertex[v];
160            }
161        }
162        (flow, cost)
163    }

Source

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

Examples found in repository ?

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

136    pub fn minimum_cost_flow_limited(&mut self, s: usize, t: usize, limit: u64) -> (u64, i64) {
137        let mut flow = 0;
138        let mut cost = 0;
139        if self.has_negedge {
140            self.bellman_ford(s);
141        }
142        while flow < limit && self.dijkstra(s, t) {
143            let shortest = self.dist[t];
144            for (p, d) in self.potential.iter_mut().zip(self.dist.iter()) {
145                *p = p.saturating_add((*d).min(shortest));
146            }
147            let mut f = limit - flow;
148            let mut v = t;
149            while v != s {
150                f = f.min(self.capacities[self.prev_edge[v]]);
151                v = self.prev_vertex[v];
152            }
153            flow += f;
154            cost += f as i64 * (self.potential[t] - self.potential[s]);
155            let mut v = t;
156            while v != s {
157                self.capacities[self.prev_edge[v]] -= f;
158                self.capacities[self.prev_edge[v] ^ 1] += f;
159                v = self.prev_vertex[v];
160            }
161        }
162        (flow, cost)
163    }

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 166)

165    pub fn minimum_cost_flow(&mut self, s: usize, t: usize) -> (u64, i64) {
166        self.minimum_cost_flow_limited(s, t, u64::MAX)
167    }

More examples

Hide additional examples

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

5pub fn grl_6_b(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(vs, es, f: u64, edges: [(usize, usize, u64, i64); iter es]);
8    let mut builder = PrimalDualBuilder::new(vs, es);
9    builder.extend(edges);
10    let graph = builder.gen_graph();
11    let mut pd = builder.build(&graph);
12    let (flow, cost) = pd.minimum_cost_flow_limited(0, vs - 1, f);
13    pp!(if flow < f { -1 } else { cost });
14}