Struct GeneralWeightedMatching

Source

pub struct GeneralWeightedMatching {
    size: usize,
    weight: Vec<Vec<i64>>,
    mate: Vec<usize>,
    matching_weight: i64,
}

Fields§

§size: usize§weight: Vec<Vec<i64>>§mate: Vec<usize>§matching_weight: i64

Implementations§

Source §

impl GeneralWeightedMatching

Source

pub fn new(size: usize) -> Self

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 33)

32    pub fn from_edges(size: usize, edges: &[(usize, usize, i64)]) -> Self {
33        let mut gm = Self::new(size);
34        for &(u, v, w) in edges {
35            gm.add_edge(u, v, w);
36        }
37        gm
38    }

More examples

Hide additional examples

crates/library_checker/src/graph/general_weighted_matching.rs (line 8)

5pub fn general_weighted_matching(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, uvw: [(usize, usize, i64); iter m]);
8    let mut gm = GeneralWeightedMatching::new(n);
9    for (u, v, w) in uvw {
10        gm.add_edge(u, v, w);
11    }
12    let (w, matching) = gm.maximum_weight_matching();
13    pp!(matching.len(), w; @ittup matching);
14}

Source

pub fn add_edge(&mut self, u: usize, v: usize, w: i64)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 35)

32    pub fn from_edges(size: usize, edges: &[(usize, usize, i64)]) -> Self {
33        let mut gm = Self::new(size);
34        for &(u, v, w) in edges {
35            gm.add_edge(u, v, w);
36        }
37        gm
38    }

More examples

Hide additional examples

crates/library_checker/src/graph/general_weighted_matching.rs (line 10)

5pub fn general_weighted_matching(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, uvw: [(usize, usize, i64); iter m]);
8    let mut gm = GeneralWeightedMatching::new(n);
9    for (u, v, w) in uvw {
10        gm.add_edge(u, v, w);
11    }
12    let (w, matching) = gm.maximum_weight_matching();
13    pp!(matching.len(), w; @ittup matching);
14}

Source

pub fn from_edges(size: usize, edges: &[(usize, usize, i64)]) -> Self

Source

pub fn maximum_weight_matching(&mut self) -> (i64, Vec<(usize, usize)>)

Examples found in repository ?

crates/library_checker/src/graph/general_weighted_matching.rs (line 12)

5pub fn general_weighted_matching(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, uvw: [(usize, usize, i64); iter m]);
8    let mut gm = GeneralWeightedMatching::new(n);
9    for (u, v, w) in uvw {
10        gm.add_edge(u, v, w);
11    }
12    let (w, matching) = gm.maximum_weight_matching();
13    pp!(matching.len(), w; @ittup matching);
14}

Source

fn compute(&mut self)

Examples found in repository ?

crates/competitive/src/graph/general_weighted_matching.rs (line 40)

39    pub fn maximum_weight_matching(&mut self) -> (i64, Vec<(usize, usize)>) {
40        self.compute();
41        let mut res = Vec::with_capacity(self.size / 2);
42        for (v, &u) in self.mate.iter().enumerate() {
43            if u != !0 && v < u {
44                res.push((v, u));
45            }
46        }
47        (self.matching_weight, res)
48    }