submodular quadratic pseudo-Boolean optimisation
(include/emthrm/graph/flow/maximum_flow/submodular_quadratic_pseudo-boolean_optimisation.hpp)

• View this file on GitHub
• Last update: 2024-04-03 22:42:26+09:00
• Include: #include "emthrm/graph/flow/maximum_flow/submodular_quadratic_pseudo-boolean_optimisation.hpp"

計算量

最大流に同じ。

仕様

template <template <typename> class C, typename T>
requires MaximumFlow<C, T>
struct SubmodularQPBO;

• C：最大流を表す構造体
• T：コストを表す型

メンバ関数

名前	効果・戻り値
explicit SubmodularQPBO(const int n);	頂点数 $N$ のオブジェクトを構築する。
void add_neq(const int u, const int v, const T cost);	$u$ が集合 $0$, $v$ が集合 $1$ に属するならばコスト $\mathrm{cost} \geq 0$ かかると定義する。
void add(const int v, bool group, T cost);	$v$ が集合 $\mathrm{group}$ に属するならばコスト $\mathrm{cost}$ かかると定義する。
void add_or(const std::vector<int>& v, const bool group, const T cost);	集合 $\mathrm{group}$ に属する頂点 $v \in V$ が存在するならばコスト $\mathrm{cost} \geq 0$ かかると定義する。
void add_or(const int u, const int v, const bool group, const T cost);	$u, v$ のいずれかまたは両方が集合 $\mathrm{group}$ に属するならばコスト $\mathrm{cost} \geq 0$ かかると定義する。
void add_eq(const std::vector<int>& v, const bool group, T cost);	$V$ に属する頂点すべてが集合 $\mathrm{group}$ に属するならばコスト $\mathrm{cost} \leq 0$ かかると定義する。
void add_eq(const int u, const int v, const bool group, const T cost);	$u, v$ 両方が集合 $\mathrm{group}$ に属するならばコスト $\mathrm{cost} \leq 0$ かかると定義する。
T solve();	最小コスト

参考文献

• https://kimiyuki.net/blog/2017/12/05/minimum-cut-and-project-selection-problem/
• https://ei1333.github.io/algorithm/dinic.html
• https://koyumeishi.hatenablog.com/entry/2021/01/14/052223
• https://twitter.com/noshi91/status/1775286389267124584

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2903/review/5292569/emthrm/C++17

Depends on

• 最大流コンセプト (include/emthrm/graph/flow/maximum_flow/maximum_flow.hpp)

Verified with

• グラフ/フロー/最大流/submodular quadratic pseudo-Boolean optimisation (test/graph/flow/maximum_flow/submodular_quadratic_pseudo-boolean_optimisation.test.cpp)

Code

#ifndef EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_SUBMODULAR_QUADRATIC_PSEUDO_BOOLEAN_OPTIMISATION_HPP_
#define EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_SUBMODULAR_QUADRATIC_PSEUDO_BOOLEAN_OPTIMISATION_HPP_

#include <cassert>
#include <limits>
#include <vector>

#include "emthrm/graph/flow/maximum_flow/maximum_flow.hpp"

namespace emthrm {

template <template <typename> class C, typename T>
requires MaximumFlow<C, T>
struct SubmodularQPBO {
  explicit SubmodularQPBO(const int n)
      : inf(std::numeric_limits<T>::max()), n(n), res(0) {}

  void add_neq(const int u, const int v, const T cost) {
    assert(cost >= 0);
    us.emplace_back(u);
    vs.emplace_back(v);
    costs.emplace_back(cost);
  }

  void add(const int v, bool group, T cost) {
    if (cost < 0) {
      cost = -cost;
      res += cost;
      group = !group;
    }
    if (group) {
      add_neq(-2, v, cost);  // -2 represents S.
    } else {
      add_neq(v, -1, cost);  // -1 represents T.
    }
  }

  void add_or(const std::vector<int>& v, const bool group, const T cost) {
    assert(cost >= 0);
    add(n, group, cost);
    if (group) {
      for (const int e : v) add_neq(n, e, inf);
    } else {
      for (const int e : v) add_neq(e, n, inf);
    }
    ++n;
  }

  void add_or(const int u, const int v, const bool group, const T cost) {
    add_or({u, v}, group, cost);
  }

  void add_eq(const std::vector<int>& v, const bool group, T cost) {
    assert(cost <= 0);
    cost = -cost;
    res += cost;
    add_or(v, !group, cost);
  }

  void add_eq(const int u, const int v, const bool group, const T cost) {
    add_eq({u, v}, group, cost);
  }

  T solve() {
    C<T> mf(n + 2);
    const int neq_size = costs.size();
    for (int i = 0; i < neq_size; ++i) {
      mf.add_edge(us[i] < 0 ? us[i] + n + 2 : us[i],
                  vs[i] < 0 ? vs[i] + n + 2 : vs[i], costs[i]);
    }
    return mf.maximum_flow(n, n + 1, inf) - res;
  }

 private:
  const T inf;
  int n;
  T res;
  std::vector<int> us, vs;
  std::vector<T> costs;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_SUBMODULAR_QUADRATIC_PSEUDO_BOOLEAN_OPTIMISATION_HPP_

#line 1 "include/emthrm/graph/flow/maximum_flow/submodular_quadratic_pseudo-boolean_optimisation.hpp"



#include <cassert>
#include <limits>
#include <vector>

#line 1 "include/emthrm/graph/flow/maximum_flow/maximum_flow.hpp"
/**
 * @title 最大流コンセプト
 */

#ifndef EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_HPP_
#define EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_HPP_

#include <concepts>
#include <utility>

namespace emthrm {

template <template <typename> class C, typename T>
concept MaximumFlow = requires (C<T> mf) {
  {mf.add_edge(std::declval<int>(), std::declval<int>(), std::declval<T>())}
      -> std::same_as<void>;
  {mf.maximum_flow(std::declval<int>(), std::declval<int>())}
      -> std::same_as<T>;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_FLOW_MAXIMUM_FLOW_MAXIMUM_FLOW_HPP_
#line 9 "include/emthrm/graph/flow/maximum_flow/submodular_quadratic_pseudo-boolean_optimisation.hpp"

namespace emthrm {

template <template <typename> class C, typename T>
requires MaximumFlow<C, T>
struct SubmodularQPBO {
  explicit SubmodularQPBO(const int n)
      : inf(std::numeric_limits<T>::max()), n(n), res(0) {}

  void add_neq(const int u, const int v, const T cost) {
    assert(cost >= 0);
    us.emplace_back(u);
    vs.emplace_back(v);
    costs.emplace_back(cost);
  }

  void add(const int v, bool group, T cost) {
    if (cost < 0) {
      cost = -cost;
      res += cost;
      group = !group;
    }
    if (group) {
      add_neq(-2, v, cost);  // -2 represents S.
    } else {
      add_neq(v, -1, cost);  // -1 represents T.
    }
  }

  void add_or(const std::vector<int>& v, const bool group, const T cost) {
    assert(cost >= 0);
    add(n, group, cost);
    if (group) {
      for (const int e : v) add_neq(n, e, inf);
    } else {
      for (const int e : v) add_neq(e, n, inf);
    }
    ++n;
  }

  void add_or(const int u, const int v, const bool group, const T cost) {
    add_or({u, v}, group, cost);
  }

  void add_eq(const std::vector<int>& v, const bool group, T cost) {
    assert(cost <= 0);
    cost = -cost;
    res += cost;
    add_or(v, !group, cost);
  }

  void add_eq(const int u, const int v, const bool group, const T cost) {
    add_eq({u, v}, group, cost);
  }

  T solve() {
    C<T> mf(n + 2);
    const int neq_size = costs.size();
    for (int i = 0; i < neq_size; ++i) {
      mf.add_edge(us[i] < 0 ? us[i] + n + 2 : us[i],
                  vs[i] < 0 ? vs[i] + n + 2 : vs[i], costs[i]);
    }
    return mf.maximum_flow(n, n + 1, inf) - res;
  }

 private:
  const T inf;
  int n;
  T res;
  std::vector<int> us, vs;
  std::vector<T> costs;
};

}  // namespace emthrm

Back to top page