Trait BitDpExt

Source

pub trait BitDpExt:
    Sized
    + Copy
    + Default
    + PartialEq
    + Eq
    + PartialOrd
    + Ord
    + Not<Output = Self>
    + BitAnd<Output = Self>
    + BitOr<Output = Self>
    + BitXor<Output = Self>
    + Shl<usize, Output = Self>
    + Shr<usize, Output = Self>
    + Add<Output = Self>
    + Sub<Output = Self>
    + Div<Output = Self>
    + Zero
    + One {
    // Provided methods
    fn contains(self, x: usize) -> bool { ... }
    fn insert(self, x: usize) -> Self { ... }
    fn remove(self, x: usize) -> Self { ... }
    fn is_subset(self, elements: Self) -> bool { ... }
    fn is_superset(self, elements: Self) -> bool { ... }
    fn subsets(self) -> Subsets<Self> ⓘ { ... }
    fn combinations(n: usize, k: usize) -> Combinations<Self> ⓘ { ... }
}

Provided Methods§

Source

fn is_subset(self, elements: Self) -> bool

Examples found in repository ?

crates/competitive/src/algorithm/bitdp.rs (line 37)

36    fn is_superset(self, elements: Self) -> bool {
37        elements.is_subset(self)
38    }

Source

fn is_superset(self, elements: Self) -> bool

Source

fn subsets(self) -> Subsets<Self> ⓘ

Examples found in repository ?

crates/competitive/src/graph/steiner_tree.rs (line 29)

8    fn steiner_tree<'a, S, M, I>(&self, terminals: I, weight: &'a M) -> SteinerTreeOutput<S, Self>
9    where
10        Self: VertexMap<S::T> + AdjacencyView<'a, M, S::T>,
11        S: ShortestPathSemiRing,
12        I: IntoIterator<Item = Self::VIndex> + ExactSizeIterator,
13    {
14        let tsize = terminals.len();
15        if tsize == 0 {
16            return SteinerTreeOutput {
17                g: self,
18                dp: vec![],
19            };
20        }
21        let mut dp: Vec<_> = repeat_with(|| self.construct_vmap(S::inf))
22            .take(1 << tsize)
23            .collect();
24        for (i, t) in terminals.into_iter().enumerate() {
25            *self.vmap_get_mut(&mut dp[1 << i], t) = S::source();
26        }
27        for bit in 1..1 << tsize {
28            for u in self.vertices() {
29                for sub in bit.subsets() {
30                    if sub != 0 {
31                        let cost =
32                            S::mul(self.vmap_get(&dp[sub], u), self.vmap_get(&dp[bit ^ sub], u));
33                        S::add_assign(self.vmap_get_mut(&mut dp[bit], u), &cost);
34                    }
35                }
36            }
37            let dp = &mut dp[bit];
38            let mut heap: BinaryHeap<_> = self
39                .vertices()
40                .map(|u| PartialIgnoredOrd(Reverse(self.vmap_get(dp, u).clone()), u))
41                .collect();
42            while let Some(PartialIgnoredOrd(Reverse(d), u)) = heap.pop() {
43                if self.vmap_get(dp, u) != &d {
44                    continue;
45                }
46                for a in self.aviews(weight, u) {
47                    let v = a.vindex();
48                    let nd = S::mul(&d, &a.avalue());
49                    if S::add_assign(self.vmap_get_mut(dp, v), &nd) {
50                        heap.push(PartialIgnoredOrd(Reverse(nd), v));
51                    }
52                }
53            }
54        }
55        SteinerTreeOutput { g: self, dp }
56    }