competitive::graph

Struct DinicBuilder

Source 
pub struct DinicBuilder { /* private fields */ }

Implementations§

Source§

impl DinicBuilder

Source

pub fn new(vsize: usize, esize_expect: usize) -> Self

Examples found in repository?
crates/competitive/src/graph/maximum_flow.rs (line 58)
57    pub fn builder(vsize: usize, esize_expect: usize) -> DinicBuilder {
58        DinicBuilder::new(vsize, esize_expect)
59    }
More examples
Hide additional examples
crates/aizu_online_judge/src/grl/grl_6_a.rs (line 10)
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}
crates/aizu_online_judge/src/grl/grl_7_a.rs (line 10)
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 10)
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}
Source

pub fn add_edge(&mut self, from: usize, to: usize, cap: u64)

Examples found in repository?
crates/competitive/src/graph/maximum_flow.rs (line 43)
41    fn extend<T: IntoIterator<Item = (usize, usize, u64)>>(&mut self, iter: T) {
42        for (from, to, cap) in iter {
43            self.add_edge(from, to, cap)
44        }
45    }
More examples
Hide additional examples
crates/aizu_online_judge/src/grl/grl_7_a.rs (line 14)
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 14)
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 102)
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 gen_graph(&mut self) -> BidirectionalSparseGraph

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_6_a.rs (line 12)
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 22)
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 22)
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 118)
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 build(self, graph: &BidirectionalSparseGraph) -> Dinic<'_>

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_6_a.rs (line 13)
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 23)
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 23)
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 119)
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    }

Trait Implementations§

Source§

impl Clone for DinicBuilder

Source§

fn clone(&self) -> DinicBuilder

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for DinicBuilder

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl Extend<(usize, usize, u64)> for DinicBuilder

Source§

fn extend<T: IntoIterator<Item = (usize, usize, u64)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator. Read more
Source§

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)
Extends a collection with exactly one element.
Source§

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)
Reserves capacity in a collection for the given number of additional elements. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.