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/// - [競プロ典型 90 問 040 - Get More Money](https://atcoder.jp/contests/typical90/tasks/typical90_an)
13///
14/// # References
15/// - [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)
16/// - [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/)
17///
18/// # Verification
19/// | function | verify |
20/// | -------- | ------ |
21/// | [`penalty_if_red`](Self::penalty_if_red) | [競プロ典型 90 問 040 #72402366](https://atcoder.jp/contests/typical90/submissions/72402366) |
22/// | [`penalty_if_blue`](Self::penalty_if_blue) | [ARC085 #27489484](https://atcoder.jp/contests/arc085/submissions/27489484) |
23/// | [`gain_if_red`](Self::gain_if_red) | [競プロ典型 90 問 040 #72402366](https://atcoder.jp/contests/typical90/submissions/72402366) |
24/// | [`gain_if_blue`](Self::gain_if_blue) | [ARC085 #27489484](https://atcoder.jp/contests/arc085/submissions/27489484) |
25/// | [`penalty_if_red_blue`](Self::penalty_if_red_blue) | |
26/// | [`penalty_if_different`](Self::penalty_if_different) | [ABC193-F #72397880](https://atcoder.jp/contests/abc193/submissions/72397880) |
27/// | [`must_be_red`](Self::must_be_red) | [ABC193-F #72397880](https://atcoder.jp/contests/abc193/submissions/72397880) |
28/// | [`must_be_blue`](Self::must_be_blue) | [ABC193-F #72397880](https://atcoder.jp/contests/abc193/submissions/72397880) |
29/// | [`if_red_then_must_be_red`](Self::if_red_then_must_be_red) | [ARC085 #27489484](https://atcoder.jp/contests/arc085/submissions/27489484) |
30/// | [`gain_if_both_red`](Self::gain_if_both_red) | |
31/// | [`gain_if_both_blue`](Self::gain_if_both_blue) | |
32
33#[derive(Clone, Debug)]
34pub struct PSP {
35    size: usize,
36    src: usize,
37    sink: usize,
38    edges: Vec<(usize, usize, u64)>,
39    node_count: usize,
40    default_gain: u64,
41}
42
43impl PSP {
44    /// `PSP`を生成する。
45    pub fn new(size: usize) -> Self {
46        Self {
47            size,
48            src: size,
49            sink: size + 1,
50            edges: vec![],
51            node_count: size + 2,
52            default_gain: 0,
53        }
54    }
55
56    /// 頂点`i`が<font color="red"><b>赤</b></font>ならば`c`の損失になる。
57    pub fn penalty_if_red(&mut self, i: usize, c: u64) {
58        assert!(i < self.size);
59        self.edges.push((i, self.sink, c));
60    }
61
62    /// 頂点`i`が<font color="blue"><b>青</b></font>ならば`c`の損失になる。
63    pub fn penalty_if_blue(&mut self, i: usize, c: u64) {
64        assert!(i < self.size);
65        self.edges.push((self.src, i, c));
66    }
67
68    /// 頂点`i`が<font color="red"><b>赤</b></font>ならば`c`の利益を得る。
69    pub fn gain_if_red(&mut self, i: usize, c: u64) {
70        assert!(i < self.size);
71        self.default_gain += c;
72        self.penalty_if_blue(i, c);
73    }
74
75    /// 頂点`i`が<font color="blue"><b>青</b></font>ならば`c`の利益を得る。
76    pub fn gain_if_blue(&mut self, i: usize, c: u64) {
77        assert!(i < self.size);
78        self.default_gain += c;
79        self.penalty_if_red(i, c);
80    }
81
82    /// 頂点`i`が<font color="red"><b>赤</b></font>かつ頂点`j`が<font color="blue"><b>青</b></font>ならば`c`の損失となる。
83    pub fn penalty_if_red_blue(&mut self, i: usize, j: usize, c: u64) {
84        assert!(i < self.size && j < self.size);
85        self.edges.push((i, j, c));
86    }
87
88    /// 頂点`i`と`j`が異なる色ならば`c`の損失となる。
89    pub fn penalty_if_different(&mut self, i: usize, j: usize, c: u64) {
90        assert!(i < self.size && j < self.size);
91        self.edges.push((i, j, c));
92        self.edges.push((j, i, c));
93    }
94
95    /// 頂点`i`は<font color="red"><b>赤</b></font>でなければならない。
96    pub fn must_be_red(&mut self, i: usize) {
97        assert!(i < self.size);
98        self.penalty_if_blue(i, u64::MAX);
99    }
100
101    /// 頂点`i`は<font color="blue"><b>青</b></font>でなければならない。
102    pub fn must_be_blue(&mut self, i: usize) {
103        assert!(i < self.size);
104        self.penalty_if_red(i, u64::MAX);
105    }
106
107    /// 頂点`i`が<font color="red"><b>赤</b></font>ならば、頂点`j`も<font color="red"><b>赤</b></font>でなければならない。
108    pub fn if_red_then_must_be_red(&mut self, i: usize, j: usize) {
109        assert!(i < self.size && j < self.size);
110        self.penalty_if_red_blue(i, j, u64::MAX);
111    }
112
113    /// 頂点`i`と`j`がともに<font color="red"><b>赤</b></font>ならば`c`の利益を得る。
114    pub fn gain_if_both_red(&mut self, i: usize, j: usize, c: u64) {
115        assert!(i < self.size && j < self.size);
116        self.default_gain += c;
117        let w = self.node_count;
118        self.node_count += 1;
119
120        self.edges.push((self.src, w, c));
121        self.edges.push((w, i, u64::MAX));
122        self.edges.push((w, j, u64::MAX));
123    }
124
125    /// 頂点`i`と`j`がともに<font color="blue"><b>青</b></font>ならば`c`の利益を得る。
126    pub fn gain_if_both_blue(&mut self, i: usize, j: usize, c: u64) {
127        assert!(i < self.size && j < self.size);
128        self.default_gain += c;
129        let w = self.node_count;
130        self.node_count += 1;
131
132        self.edges.push((w, self.sink, c));
133        self.edges.push((i, w, u64::MAX));
134        self.edges.push((j, w, u64::MAX));
135    }
136
137    /// must be制約を破った場合、`None`を返す。そうでなければ、利益の最大値を`Some`に包んで返す。
138    pub fn solve<F: MaxFlow<Cap = u64>>(self) -> Option<i64> {
139        let mut f = F::new(self.node_count);
140        for (u, v, c) in self.edges {
141            f.add_edge(u, v, c);
142        }
143
144        let flow = f.max_flow(self.src, self.sink);
145
146        if flow == u64::MAX {
147            None
148        } else {
149            Some(self.default_gain as i64 - flow as i64)
150        }
151    }
152}
haar_lib/algo/psp.rs

haar_lib/algo/
psp.rs
