Struct PSP

pub struct PSP { /* private fields */ }

Project Selection Problem

Problems

• ARC 085 E - MUL
• AOJ 3058 Ghost
• AOJ 2903 Board
• ABC 193 F - Zebraness

References

• https://ferin-tech.hatenablog.com/entry/2019/10/28/燃やす埋める問題
• https://kmyk.github.io/blog/blog/2017/12/05/minimum-cut-and-project-selection-problem/

Verification

function	verify
penalty_if_red
penalty_if_blue	ARC085 #27489484
gain_if_red
gain_if_blue	ARC085 #27489484
penalty_if_red_blue
penalty_if_different
must_be_red
must_be_blue
if_red_then_must_be_red	ARC085 #27489484
gain_if_both_red
gain_if_both_blue

Implementations

impl PSP

pub fn new(size: usize) -> Self

PSPを生成する。

pub fn penalty_if_red(&mut self, i: usize, c: u64)

頂点iが赤ならばcの損失になる。

pub fn penalty_if_blue(&mut self, i: usize, c: u64)

頂点iが青ならばcの損失になる。

pub fn gain_if_red(&mut self, i: usize, c: u64)

頂点iが赤ならばcの利益を得る。

pub fn gain_if_blue(&mut self, i: usize, c: u64)

頂点iが青ならばcの利益を得る。

pub fn penalty_if_red_blue(&mut self, i: usize, j: usize, c: u64)

頂点iが赤かつ頂点jが青ならばcの損失となる。

pub fn penalty_if_different(&mut self, i: usize, j: usize, c: u64)

頂点iとjが異なる色ならばcの損失となる。

pub fn must_be_red(&mut self, i: usize)

頂点iは赤でなければならない。

pub fn must_be_blue(&mut self, i: usize)

頂点iは青でなければならない。

pub fn if_red_then_must_be_red(&mut self, i: usize, j: usize)

頂点iが赤ならば、頂点jも赤でなければならない。

pub fn gain_if_both_red(&mut self, i: usize, j: usize, c: u64)

頂点iとjがともに赤ならばcの利益を得る。

pub fn gain_if_both_blue(&mut self, i: usize, j: usize, c: u64)

頂点iとjがともに青ならばcの利益を得る。

pub fn solve<F: MaxFlow<Cap = u64>>(self) -> Option<i64>

must be制約を破った場合、Noneを返す。そうでなければ、利益の最大値をSomeに包んで返す。

Trait Implementations

impl Clone for PSP

fn clone(&self) -> PSP

Returns a copy of the value.

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

Performs copy-assignment from source.