cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
Binary Optimization (Project Selection Problem)
(src/optimization/BinaryOptimization.hpp)
- View this file on GitHub
- Last update: 2024-06-01 01:35:37+09:00
- Include:
#include "src/optimization/BinaryOptimization.hpp"
add(i, j, k, x), add_all_0(is, x), add_all_1(is, x) は未 verify につき注意
概要
Project Selection Problem，いわゆる燃やす埋める問題を解く際の補助ライブラリ． 具体的には $n$ 個の $01$ 変数 $x _ 1, \dots , x _ n$ に対して各種損失条件が与えられる際に損失を最小化する割当を求める． すなわち，$\alpha \in \mathbb{Z}, \theta _ i \colon \lbrace 0, 1 \rbrace \to \mathbb{Z}, \phi _ {i, j} \colon \lbrace 0, 1 \rbrace ^ 2 \to \mathbb{Z}, \psi _ {i, j, k} \colon \lbrace 0, 1 \rbrace ^ 3 \to \mathbb{Z}$ について，
\[\begin{alignedat}{3} & \mathrm{Minimize} & \quad & \alpha + \sum _ i \theta _ i(x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) + \sum _ {i \lt j \lt k} \psi _ {i, j, k}(x _ i, x _ j, x _ k) \\ & \mathrm{subject\ to} & \quad & x \in \lbrace 0, 1 \rbrace ^ n \end{alignedat}\]を解く． また，$x _ {i _ 1} = x _ {i _ 2} = \dots x _ {i _ m}$ のときにのみ $c$ を減らすような関数も考慮可能である．
頂点 $i$ から $j$ への容量 $c$ の辺は $x _ i = 0$ かつ $x _ j = 1$ のときにのみコスト $c$ を発生させるものと考えると良い．
最大化したい場合は template 引数の MINIMIZE を false にする．
| メンバ関数 | 効果 | 時間計算量 |
|---|---|---|
BinaryOptimization(n) |
頂点数 $n$ のグラフとして初期化する． | $\mathrm{O}(n)$ |
add(x) |
$\alpha$ に $x$ を加える． | $\mathrm{O}(1)$ |
add(i, x) |
$\theta _ i$ を設定する． | $\mathrm{O}(1)$ |
add(i, j, x) |
$\phi _ {i, j}$ を設定する． | $\mathrm{O}(1)$ |
add(i, j, k, x) |
$\psi _ {i, j, k}$ を設定する． | $\mathrm{O}(1)$ |
add_all_0(is, x) |
$\textit{is}$ の要素が全て $0$ のときに $x$ を得る． | $\mathrm{O}(\vert \textit{is} \vert)$ |
add_all_1(is, x) |
$\textit{is}$ の要素が全て $1$ のときに $x$ を得る． | $\mathrm{O}(\vert \textit{is} \vert)$ |
solve() |
損失の最小値及びそれを達成する割当を返す． | $\mathrm{O}(n^2m)$ |
solve() の計算量に現れる $n, m$ はそれぞれできあがったネットワークの頂点の個数，辺の本数である．
一般にこれ以外の条件に対応する際には 2 部グラフなどの制約が必要になる．
出題例
- Codeforces Round #668 (Div. 1) E. Bricks
- AtCoder Regular Contest 085 E - MUL
- AtCoder Grand Contest 038 F - Two Permutations
- AtCoder Regular Contest 107 F - Sum of Abs
- 2023牛客暑期多校训练营2 B Link with Railway Company
- AtCoder Regular Contest 176 E - Max Vector
Links
- 最小カットを使って「燃やす埋める問題」を解く
- 最小カットについて - よすぽの日記
- Project Selection (燃やす埋める) 周りの話についてもう少し考えた - とこはるのまとめ
- 続：『燃やす埋める』と『ProjectSelectionProblem』 - とこはるのまとめ
- 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性 その① - 私と理論
Required by
$K$-ary Optimization
(src/optimization/KaryOptimization.hpp)
Verified with
Code
#pragma once
#include <array>
#include <tuple>
#include "../atcoder/maxflow"
template <typename T, bool MINIMIZE = true> struct BinaryOptimization {
BinaryOptimization() = default;
explicit BinaryOptimization(int n) : n(n) {}
void add(T x) {
if (not MINIMIZE) x = -x;
_add(x);
}
void add(int i, std::array<T, 2> x) {
assert(0 <= i and i < n);
if (not MINIMIZE) {
for (int i = 0; i < 2; i++) {
x[i] = -x[i];
}
}
_add(i, x);
}
void add_01(int i, int j, T x) {
assert(0 <= i and i < n);
assert(0 <= j and j < n);
if (not MINIMIZE) x = -x;
assert(x >= 0);
add_edge(i, j, x);
}
void add_10(int i, int j, T x) { add_01(j, i, x); }
void add(int i, int j, std::array<std::array<T, 2>, 2> x) {
assert(0 <= i and i < n);
assert(0 <= j and j < n);
if (not MINIMIZE) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
x[i][j] = -x[i][j];
}
}
}
assert(x[0][1] + x[1][0] >= x[0][0] + x[1][1]);
_add(i, j, x);
}
void add(int i, int j, int k, std::array<std::array<std::array<T, 2>, 2>, 2> x) {
assert(0 <= i and i < n);
assert(0 <= j and j < n);
assert(0 <= k and k < n);
if (not MINIMIZE) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
x[i][j][k] = -x[i][j][k];
}
}
}
}
_add(i, j, k, x);
}
void add_all_0(const std::vector<int>& is, T x) {
if (not MINIMIZE) x = -x;
assert(x <= 0);
if (is.size() == 0)
_add(x);
else if (is.size() == 1)
_add(is[0], {x, 0});
else if (is.size() == 2)
_add(is[0], is[1], {x, 0, 0, 0});
else {
_add(x);
int nxt = n + aux++;
add_edge(source, nxt, -x);
for (const int& i : is) {
assert(0 <= i and i < n);
add_edge(nxt, i, -x);
}
}
}
void add_all_1(const std::vector<int>& is, T x) {
if (not MINIMIZE) x = -x;
assert(x <= 0);
if (is.size() == 0)
_add(x);
else if (is.size() == 1)
_add(is[0], {0, x});
else if (is.size() == 2)
_add(is[0], is[1], {0, 0, 0, x});
else {
_add(x);
int nxt = n + aux++;
add_edge(nxt, sink, -x);
for (const int& i : is) {
assert(0 <= i and i < n);
add_edge(i, nxt, -x);
}
}
}
std::pair<T, std::vector<bool>> solve() {
atcoder::mf_graph<T> g(n + aux + 2);
int s = n + aux, t = s + 1;
for (auto [u, v, w] : es) {
u = (u == source ? s : u == sink ? t : u);
v = (v == source ? s : v == sink ? t : v);
g.add_edge(u, v, w);
}
T sum = base + g.flow(s, t);
auto cut = g.min_cut(s);
cut.resize(n);
for (int i = 0; i < n; i++) cut[i] = not cut[i];
if (not MINIMIZE) sum = -sum;
return {sum, cut};
}
private:
int n, aux = 0, source = -1, sink = -2;
T base = 0;
std::vector<std::tuple<int, int, T>> es;
void add_edge(int i, int j, T x) {
assert(i == source or i == sink or (0 <= i and i < n + aux));
assert(j == source or j == sink or (0 <= j and j < n + aux));
if (x == 0) return;
assert(x > 0);
es.emplace_back(i, j, x);
}
void _add(T x) { base += x; }
void _add(int i, const std::array<T, 2>& x) {
if (x[0] <= x[1]) {
_add(x[0]);
add_edge(source, i, x[1] - x[0]);
} else {
_add(x[1]);
add_edge(i, sink, x[0] - x[1]);
}
}
void _add(int i, int j, const std::array<std::array<T, 2>, 2>& x) {
_add(i, {x[0][0], x[1][0]});
_add(j, {0, x[1][1] - x[1][0]});
add_edge(i, j, (x[0][1] + x[1][0]) - (x[0][0] + x[1][1]));
}
void _add(int i, int j, int k, const std::array<std::array<std::array<T, 2>, 2>, 2>& x) {
T P = x[0][0][0] - (x[1][0][0] + x[0][1][0] + x[0][0][1]) + (x[1][1][0] + x[0][1][1] + x[1][0][1]) - x[1][1][1];
if (P >= 0) {
_add(x[0][0][0]);
_add(i, {0, x[1][0][0] - x[0][0][0]});
_add(j, {0, x[0][1][0] - x[0][0][0]});
_add(k, {0, x[0][0][1] - x[0][0][0]});
_add(i, j, {0, 0, 0, (x[0][0][0] + x[1][1][0]) - (x[1][0][0] + x[0][1][0])});
_add(j, k, {0, 0, 0, (x[0][0][0] + x[0][1][1]) - (x[0][1][0] + x[0][0][1])});
_add(k, i, {0, 0, 0, (x[0][0][0] + x[1][0][1]) - (x[0][0][1] + x[1][0][0])});
_add(-P);
int nxt = n + aux++;
add_edge(i, nxt, P);
add_edge(j, nxt, P);
add_edge(k, nxt, P);
add_edge(nxt, sink, P);
} else {
_add(x[1][1][1]);
_add(i, {x[0][1][1] - x[1][1][1], 0});
_add(j, {x[1][0][1] - x[1][1][1], 0});
_add(k, {x[1][1][0] - x[1][1][1], 0});
_add(i, j, {(x[1][1][1] + x[0][0][1]) - (x[0][1][1] + x[1][0][1]), 0, 0, 0});
_add(j, k, {(x[1][1][1] + x[1][0][0]) - (x[1][0][1] + x[1][1][0]), 0, 0, 0});
_add(k, i, {(x[1][1][1] + x[0][1][0]) - (x[1][1][0] + x[0][1][1]), 0, 0, 0});
P = -P;
_add(-P);
int nxt = n + aux++;
add_edge(nxt, i, P);
add_edge(nxt, j, P);
add_edge(nxt, k, P);
add_edge(source, nxt, P);
}
}
};Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
bundler.update(path)
~~~~~~~~~~~~~~^^^^^^
File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
self.update(self._resolve(pathlib.Path(included), included_from=path))
~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
self.update(self._resolve(pathlib.Path(included), included_from=path))
~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/maxflow.hpp: line -1: no such header