Struct ProjectSelectionProblem

pub struct ProjectSelectionProblem { /* private fields */ }

Implementations

impl ProjectSelectionProblem

pub fn new(n_project: usize, n_value: usize) -> Self

pub fn with_n_values(n_values: Vec<usize>) -> Self

pub fn add_cost1(&mut self, p: usize, v: usize, c: i64)

Examples found in repository

crates/competitive/src/graph/project_selection_problem.rs (line 68)

    pub fn add_cost2<F>(&mut self, p1: usize, p2: usize, mut cost: F)
    where
        F: FnMut(usize, usize) -> i64,
    {
        debug_assert_ne!(p1, p2);
        let nv1 = self.n_values[p1];
        let nv2 = self.n_values[p2];
        debug_assert_ne!(nv1, 0);
        debug_assert_ne!(nv2, 0);
        let c00 = cost(0, 0);
        self.totalcost += c00;
        for v1 in 1usize..nv1 {
            self.add_cost1(p1, v1, cost(v1, 0) - c00);
        }
        for v2 in 1usize..nv2 {
            self.add_cost1(p2, v2, cost(0, v2) - c00);
        }
        let mut acc = 0i64;
        for v1 in 1usize..nv1 {
            for v2 in 1usize..nv2 {
                let c = cost(v1 - 1, v2) + cost(v1, v2 - 1) - cost(v1, v2) - cost(v1 - 1, v2 - 1);
                debug_assert!(c >= 0, "cost is not monge");
                let key = (self.start[p1] + v1 - 1, self.start[p2] + v2 - 1);
                if c > 0 {
                    *self.cost2.entry(key).or_default() += c as u64;
                }
                acc -= c;
            }
            self.add_cost1(p1, v1, acc);
        }
    }

pub fn add_cost2_01( &mut self, p1: usize, p2: usize, v1: usize, v2: usize, c: u64, )

x1 >= v1 && x2 < v2 (0 < v1 < nv1, 0 < v2 < nv2)

Examples found in repository

crates/competitive/src/graph/project_selection_problem.rs (line 53)

    pub fn add_cost2_10(&mut self, p1: usize, p2: usize, v1: usize, v2: usize, c: u64) {
        self.add_cost2_01(p2, p1, v2, v1, c);
    }

pub fn add_cost2_10( &mut self, p1: usize, p2: usize, v1: usize, v2: usize, c: u64, )

x1 < v1 && x2 >= v2 (0 < v1 < nv1, 0 < v2 < nv2)

pub fn add_cost2<F>(&mut self, p1: usize, p2: usize, cost: F)

where F: FnMut(usize, usize) -> i64,

cost is monge: cost(v1-1, v2) + cost(v1, v2-1) >= cost(v1, v2) + cost(v1-1, v2-1)

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

Trait Implementations

impl Clone for ProjectSelectionProblem

fn clone(&self) -> ProjectSelectionProblem

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ProjectSelectionProblem

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

Formats the value using the given formatter.

impl Default for ProjectSelectionProblem

fn default() -> ProjectSelectionProblem

Returns the “default value” for a type.