haar_lib/algo/
psp.rs

1//! Project Selection Problem
2
3use crate::flow::*;
4
5/// Project Selection Problem
6///
7/// # Problems
8/// - [ARC 085 E - MUL](https://atcoder.jp/contests/arc085/tasks/arc085_c)
9/// - [AOJ 3058 Ghost](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3058)
10/// - [AOJ 2903 Board](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2903)
11/// - [ABC 193 F - Zebraness](https://atcoder.jp/contests/abc193/tasks/abc193_f)
12///
13/// # References
14/// - [https://ferin-tech.hatenablog.com/entry/2019/10/28/燃やす埋める問題](https://ferin-tech.hatenablog.com/entry/2019/10/28/%E7%87%83%E3%82%84%E3%81%99%E5%9F%8B%E3%82%81%E3%82%8B%E5%95%8F%E9%A1%8C)
15/// - [https://kmyk.github.io/blog/blog/2017/12/05/minimum-cut-and-project-selection-problem/](https://kmyk.github.io/blog/blog/2017/12/05/minimum-cut-and-project-selection-problem/)
16///
17/// # Verification
18/// | function | verify |
19/// | -------- | ------ |
20/// | `penalty_if_red` | |
21/// | `penalty_if_blue` | [ARC085 #27489484](https://atcoder.jp/contests/arc085/submissions/27489484) |
22/// | `gain_if_red` | |
23/// | `gain_if_blue` | [ARC085 #27489484](https://atcoder.jp/contests/arc085/submissions/27489484) |
24/// | `penalty_if_red_blue` | |
25/// | `penalty_if_different` | |
26/// | `must_be_red` | |
27/// | `must_be_blue` | |
28/// | `if_red_then_must_be_red` | [ARC085 #27489484](https://atcoder.jp/contests/arc085/submissions/27489484) |
29/// | `gain_if_both_red` | |
30/// | `gain_if_both_blue` | |
31
32#[derive(Clone)]
33pub struct PSP {
34    size: usize,
35    src: usize,
36    sink: usize,
37    edges: Vec<(usize, usize, u64)>,
38    node_count: usize,
39    default_gain: u64,
40}
41
42impl PSP {
43    /// `PSP`を生成する。
44    pub fn new(size: usize) -> Self {
45        Self {
46            size,
47            src: size,
48            sink: size + 1,
49            edges: vec![],
50            node_count: size + 2,
51            default_gain: 0,
52        }
53    }
54
55    /// 頂点iが<font color="red"><b>赤</b></font>ならばcの損失になる。
56    pub fn penalty_if_red(&mut self, i: usize, c: u64) {
57        assert!(i < self.size);
58        self.edges.push((i, self.sink, c));
59    }
60
61    /// 頂点iが<font color="blue"><b>青</b></font>ならばcの損失になる。
62    pub fn penalty_if_blue(&mut self, i: usize, c: u64) {
63        assert!(i < self.size);
64        self.edges.push((self.src, i, c));
65    }
66
67    /// 頂点iが<font color="red"><b>赤</b></font>ならばcの利益を得る。
68    pub fn gain_if_red(&mut self, i: usize, c: u64) {
69        assert!(i < self.size);
70        self.default_gain += c;
71        self.penalty_if_blue(i, c);
72    }
73
74    /// 頂点iが<font color="blue"><b>青</b></font>ならばcの利益を得る。
75    pub fn gain_if_blue(&mut self, i: usize, c: u64) {
76        assert!(i < self.size);
77        self.default_gain += c;
78        self.penalty_if_red(i, c);
79    }
80
81    /// 頂点iが<font color="red"><b>赤</b></font>かつ頂点jが<font color="blue"><b>青</b></font>ならばcの損失となる。
82    pub fn penalty_if_red_blue(&mut self, i: usize, j: usize, c: u64) {
83        assert!(i < self.size && j < self.size);
84        self.edges.push((i, j, c));
85    }
86
87    /// 頂点iとjが異なる色ならばcの損失となる。
88    pub fn penalty_if_different(&mut self, i: usize, j: usize, c: u64) {
89        assert!(i < self.size && j < self.size);
90        self.edges.push((i, j, c));
91        self.edges.push((j, i, c));
92    }
93
94    /// 頂点iは<font color="red"><b>赤</b></font>でなければならない。
95    pub fn must_be_red(&mut self, i: usize) {
96        assert!(i < self.size);
97        self.penalty_if_blue(i, u64::MAX);
98    }
99
100    /// 頂点iは<font color="blue"><b>青</b></font>でなければならない。
101    pub fn must_be_blue(&mut self, i: usize) {
102        assert!(i < self.size);
103        self.penalty_if_red(i, u64::MAX);
104    }
105
106    /// 頂点iが<font color="red"><b>赤</b></font>ならば、頂点jも<font color="red"><b>赤</b></font>でなければならない。
107    pub fn if_red_then_must_be_red(&mut self, i: usize, j: usize) {
108        assert!(i < self.size && j < self.size);
109        self.penalty_if_red_blue(i, j, u64::MAX);
110    }
111
112    /// 頂点iとjがともに<font color="red"><b>赤</b></font>ならばcの利益を得る。
113    pub fn gain_if_both_red(&mut self, i: usize, j: usize, c: u64) {
114        assert!(i < self.size && j < self.size);
115        self.default_gain += c;
116        let w = self.node_count;
117        self.node_count += 1;
118
119        self.edges.push((self.src, w, c));
120        self.edges.push((w, i, u64::MAX));
121        self.edges.push((w, j, u64::MAX));
122    }
123
124    /// 頂点iとjがともに<font color="blue"><b>青</b></font>ならばcの利益を得る。
125    pub fn gain_if_both_blue(&mut self, i: usize, j: usize, c: u64) {
126        assert!(i < self.size && j < self.size);
127        self.default_gain += c;
128        let w = self.node_count;
129        self.node_count += 1;
130
131        self.edges.push((w, self.sink, c));
132        self.edges.push((i, w, u64::MAX));
133        self.edges.push((j, w, u64::MAX));
134    }
135
136    /// must be制約を破った場合、`None`を返す。そうでなければ、利益の最大値を`Some`に包んで返す。
137    pub fn solve<F: MaxFlow<Cap = u64>>(self) -> Option<i64> {
138        let mut f = F::new(self.node_count);
139        for (u, v, c) in self.edges {
140            f.add_edge(u, v, c);
141        }
142
143        let flow = f.max_flow(self.src, self.sink);
144
145        if flow == u64::MAX {
146            None
147        } else {
148            Some(self.default_gain as i64 - flow as i64)
149        }
150    }
151}
haar_lib/algo/psp.rs

haar_lib/algo/
psp.rs
