haar_lib/graph/
chinese_postman.rs

1//! 中国人郵便配達問題
2
3#![allow(clippy::needless_range_loop)]
4
5use crate::graph::*;
6use crate::num::one_zero::Zero;
7use std::ops::Add;
8
9/// **Time complexity** $O(V^2 2^V)$
10pub fn chinese_postman_problem<E: EdgeTrait>(g: &Graph<Undirected, E>) -> E::Weight
11where
12    E::Weight: Copy + Ord + Add<Output = E::Weight> + Zero,
13{
14    let n = g.len();
15    let zero = E::Weight::zero();
16
17    let mut dist = vec![vec![None; n]; n];
18
19    for i in 0..n {
20        dist[i][i] = Some(zero);
21    }
22
23    for e in g.nodes_iter().flat_map(|v| &v.edges) {
24        let (from, to, cost) = (e.from(), e.to(), e.weight());
25        dist[from][to] = dist[from][to].map(|x| x.min(cost)).or(Some(cost));
26    }
27
28    for k in 0..n {
29        for i in 0..n {
30            for j in 0..n {
31                if let (Some(x), Some(y)) = (dist[i][k], dist[k][j]) {
32                    dist[i][j] = dist[i][j].map(|z| z.min(x + y)).or(Some(x + y))
33                }
34            }
35        }
36    }
37
38    let odd: Vec<_> = g
39        .nodes_iter()
40        .enumerate()
41        .filter_map(|(i, es)| (es.edges.len() % 2 == 1).then_some(i))
42        .collect();
43    let m = odd.len();
44
45    let mut dp = vec![None; 1 << m];
46    dp[0] = Some(zero);
47
48    for i in 0..1 << m {
49        for j in 0..m {
50            for k in 0..j {
51                if (i & (1 << j)) == 0 || (i & (1 << k)) == 0 {
52                    continue;
53                }
54
55                if let Some(d) = dp[i ^ (1 << j) ^ (1 << k)] {
56                    let d = d + dist[odd[j]][odd[k]].unwrap();
57                    dp[i] = dp[i].map(|x| x.min(d)).or(Some(d));
58                }
59            }
60        }
61    }
62
63    g.nodes_iter()
64        .flat_map(|es| {
65            es.edges
66                .iter()
67                .filter_map(|e| (e.from() <= e.to()).then_some(e.weight()))
68        })
69        .fold(dp[(1 << m) - 1].unwrap(), |x, y| x + y)
70}
71
72#[cfg(test)]
73mod tests {
74    use super::*;
75
76    #[test]
77    fn test() {
78        // https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_B/
79        let mut g = Graph::<Undirected, _>::new(4);
80        g.extend(
81            vec![(0, 1, 1), (0, 2, 2), (1, 3, 3), (2, 3, 4)]
82                .into_iter()
83                .map(|(u, v, w)| Edge::new(u, v, w, ())),
84        );
85        assert_eq!(chinese_postman_problem(&g), 10);
86
87        let mut g = Graph::<Undirected, _>::new(4);
88        g.extend(
89            vec![(0, 1, 1), (0, 2, 2), (1, 3, 3), (2, 3, 4), (1, 2, 5)]
90                .into_iter()
91                .map(|(u, v, w)| Edge::new(u, v, w, ())),
92        );
93        assert_eq!(chinese_postman_problem(&g), 18);
94
95        let mut g = Graph::<Undirected, _>::new(2);
96        g.extend(
97            vec![(0, 1, 1), (0, 1, 2), (0, 1, 3)]
98                .into_iter()
99                .map(|(u, v, w)| Edge::new(u, v, w, ())),
100        );
101        assert_eq!(chinese_postman_problem(&g), 7);
102    }
103}
haar_lib/graph/chinese_postman.rs

haar_lib/graph/
chinese_postman.rs
