competitive::graph::general_weighted_matching

Struct GeneralWeightedMatching

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    }

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    }

Source

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

Examples found in repository ?

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

6pub fn general_weighted_matching(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, uvw: [(usize, usize, i64); m]);
10    let mut gm = GeneralWeightedMatching::from_edges(n, &uvw);
11    let (w, matching) = gm.maximum_weight_matching();
12    writeln!(writer, "{} {}", matching.len(), w).ok();
13    for (u, v) in matching {
14        writeln!(writer, "{} {}", u, v).ok();
15    }
16}

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

6pub fn general_weighted_matching(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, m, uvw: [(usize, usize, i64); m]);
10    let mut gm = GeneralWeightedMatching::from_edges(n, &uvw);
11    let (w, matching) = gm.maximum_weight_matching();
12    writeln!(writer, "{} {}", matching.len(), w).ok();
13    for (u, v) in matching {
14        writeln!(writer, "{} {}", u, v).ok();
15    }
16}

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 in 0..self.size {
43            let u = self.mate[v];
44            if u != !0 && v < u {
45                res.push((v, u));
46            }
47        }
48        (self.matching_weight, res)
49    }