Struct Dinic

Source

pub struct Dinic<'a> { /* private fields */ }

Implementations§

Source §

impl Dinic<'_>

Source

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

Examples found in repository ?

crates/competitive/src/graph/project_selection_problem.rs (line 90)

87    pub fn solve(&self) -> (i64, Vec<usize>) {
88        let vsize = *self.start.last().unwrap();
89        let esize_expect = vsize * 2 + self.cost2.len();
90        let mut builder = Dinic::builder(vsize + 2, esize_expect);
91        let mut totalcost = self.totalcost;
92        let s = vsize;
93        let t = s + 1;
94        for (p, c) in self.cost1.iter().enumerate() {
95            let nv = self.n_values[p];
96            totalcost += c[nv - 1];
97            for v in 1usize..nv {
98                let u = self.start[p] + v - 1;
99                let d = c[v] - c[v - 1];
100                match d.cmp(&0) {
101                    Ordering::Less => {
102                        builder.add_edge(s, u, (-d) as u64);
103                    }
104                    Ordering::Greater => {
105                        builder.add_edge(u, t, d as u64);
106                        totalcost -= d;
107                    }
108                    Ordering::Equal => {}
109                }
110                if v >= 2 {
111                    builder.add_edge(u, u - 1, u64::MAX);
112                }
113            }
114        }
115        for (&(x, y), &c) in self.cost2.iter() {
116            builder.add_edge(x, y, c);
117        }
118        let dgraph = builder.gen_graph();
119        let mut dinic = builder.build(&dgraph);
120        let res = dinic.maximum_flow(s, t) as i64 + totalcost;
121        let visited = dinic.minimum_cut(s);
122        let mut values = vec![0usize; self.n_values.len()];
123        for (p, &nv) in self.n_values.iter().enumerate() {
124            for v in 1usize..nv {
125                values[p] += visited[self.start[p] + v - 1] as usize;
126            }
127        }
128        (res, values)
129    }

Source

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

Examples found in repository ?

crates/competitive/src/graph/maximum_flow.rs (line 119)

118    pub fn maximum_flow(&mut self, s: usize, t: usize) -> u64 {
119        self.maximum_flow_limited(s, t, u64::MAX)
120    }

Source

pub fn maximum_flow(&mut self, s: usize, t: usize) -> u64

Examples found in repository ?

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

6pub fn grl_6_a(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, edges: [(usize, usize, u64)]);
10    let mut builder = DinicBuilder::new(vs, es);
11    builder.extend(edges.take(es));
12    let graph = builder.gen_graph();
13    let mut dinic = builder.build(&graph);
14    writeln!(writer, "{}", dinic.maximum_flow(0, vs - 1)).ok();
15}

More examples

Hide additional examples

crates/aizu_online_judge/src/grl/grl_7_a.rs (line 24)

6pub fn grl_7_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, xs, ys, es, edges: [(usize, usize)]);
10    let mut builder = DinicBuilder::new(xs + ys + 2, xs + ys + es);
11    let s = xs + ys;
12    let t = s + 1;
13    for x in 0..xs {
14        builder.add_edge(s, x, 1);
15    }
16    for y in 0..ys {
17        builder.add_edge(y + xs, t, 1);
18    }
19    for (x, y) in edges.take(es) {
20        builder.add_edge(x, y + xs, 1);
21    }
22    let graph = builder.gen_graph();
23    let mut dinic = builder.build(&graph);
24    writeln!(writer, "{}", dinic.maximum_flow(s, t)).ok();
25}

crates/library_checker/src/graph/bipartitematching.rs (line 24)

6pub fn bipartitematching_dinic(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, l, r, m, ab: [(usize, usize); m]);
10    let mut builder = DinicBuilder::new(l + r + 2, m + l + r);
11    let s = l + r;
12    let t = s + 1;
13    for (a, b) in ab.iter().cloned() {
14        builder.add_edge(a, b + l, 1);
15    }
16    for a in 0..l {
17        builder.add_edge(s, a, 1);
18    }
19    for b in 0..r {
20        builder.add_edge(b + l, t, 1);
21    }
22    let graph = builder.gen_graph();
23    let mut dinic = builder.build(&graph);
24    let f = dinic.maximum_flow(s, t);
25    writeln!(writer, "{}", f).ok();
26    for (i, (a, b)) in ab.iter().enumerate() {
27        if dinic.get_flow(i) > 0 {
28            writeln!(writer, "{} {}", a, b).ok();
29        }
30    }
31}

crates/competitive/src/graph/project_selection_problem.rs (line 120)

87    pub fn solve(&self) -> (i64, Vec<usize>) {
88        let vsize = *self.start.last().unwrap();
89        let esize_expect = vsize * 2 + self.cost2.len();
90        let mut builder = Dinic::builder(vsize + 2, esize_expect);
91        let mut totalcost = self.totalcost;
92        let s = vsize;
93        let t = s + 1;
94        for (p, c) in self.cost1.iter().enumerate() {
95            let nv = self.n_values[p];
96            totalcost += c[nv - 1];
97            for v in 1usize..nv {
98                let u = self.start[p] + v - 1;
99                let d = c[v] - c[v - 1];
100                match d.cmp(&0) {
101                    Ordering::Less => {
102                        builder.add_edge(s, u, (-d) as u64);
103                    }
104                    Ordering::Greater => {
105                        builder.add_edge(u, t, d as u64);
106                        totalcost -= d;
107                    }
108                    Ordering::Equal => {}
109                }
110                if v >= 2 {
111                    builder.add_edge(u, u - 1, u64::MAX);
112                }
113            }
114        }
115        for (&(x, y), &c) in self.cost2.iter() {
116            builder.add_edge(x, y, c);
117        }
118        let dgraph = builder.gen_graph();
119        let mut dinic = builder.build(&dgraph);
120        let res = dinic.maximum_flow(s, t) as i64 + totalcost;
121        let visited = dinic.minimum_cut(s);
122        let mut values = vec![0usize; self.n_values.len()];
123        for (p, &nv) in self.n_values.iter().enumerate() {
124            for v in 1usize..nv {
125                values[p] += visited[self.start[p] + v - 1] as usize;
126            }
127        }
128        (res, values)
129    }

Source

pub fn minimum_cut(&mut self, s: usize) -> Vec<bool>

Examples found in repository ?

crates/competitive/src/graph/project_selection_problem.rs (line 121)

87    pub fn solve(&self) -> (i64, Vec<usize>) {
88        let vsize = *self.start.last().unwrap();
89        let esize_expect = vsize * 2 + self.cost2.len();
90        let mut builder = Dinic::builder(vsize + 2, esize_expect);
91        let mut totalcost = self.totalcost;
92        let s = vsize;
93        let t = s + 1;
94        for (p, c) in self.cost1.iter().enumerate() {
95            let nv = self.n_values[p];
96            totalcost += c[nv - 1];
97            for v in 1usize..nv {
98                let u = self.start[p] + v - 1;
99                let d = c[v] - c[v - 1];
100                match d.cmp(&0) {
101                    Ordering::Less => {
102                        builder.add_edge(s, u, (-d) as u64);
103                    }
104                    Ordering::Greater => {
105                        builder.add_edge(u, t, d as u64);
106                        totalcost -= d;
107                    }
108                    Ordering::Equal => {}
109                }
110                if v >= 2 {
111                    builder.add_edge(u, u - 1, u64::MAX);
112                }
113            }
114        }
115        for (&(x, y), &c) in self.cost2.iter() {
116            builder.add_edge(x, y, c);
117        }
118        let dgraph = builder.gen_graph();
119        let mut dinic = builder.build(&dgraph);
120        let res = dinic.maximum_flow(s, t) as i64 + totalcost;
121        let visited = dinic.minimum_cut(s);
122        let mut values = vec![0usize; self.n_values.len()];
123        for (p, &nv) in self.n_values.iter().enumerate() {
124            for v in 1usize..nv {
125                values[p] += visited[self.start[p] + v - 1] as usize;
126            }
127        }
128        (res, values)
129    }

Source

pub fn get_flow(&self, eid: usize) -> u64

Examples found in repository ?

crates/library_checker/src/graph/bipartitematching.rs (line 27)

6pub fn bipartitematching_dinic(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, l, r, m, ab: [(usize, usize); m]);
10    let mut builder = DinicBuilder::new(l + r + 2, m + l + r);
11    let s = l + r;
12    let t = s + 1;
13    for (a, b) in ab.iter().cloned() {
14        builder.add_edge(a, b + l, 1);
15    }
16    for a in 0..l {
17        builder.add_edge(s, a, 1);
18    }
19    for b in 0..r {
20        builder.add_edge(b + l, t, 1);
21    }
22    let graph = builder.gen_graph();
23    let mut dinic = builder.build(&graph);
24    let f = dinic.maximum_flow(s, t);
25    writeln!(writer, "{}", f).ok();
26    for (i, (a, b)) in ab.iter().enumerate() {
27        if dinic.get_flow(i) > 0 {
28            writeln!(writer, "{} {}", a, b).ok();
29        }
30    }
31}