Project selection problem
(Mylib/Graph/project_selection_problem.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

• project_selection_problem(N)
• penalty_if_red(int i, T c)
  • iを赤に塗るとcの損失になる。
• gain_if_red(int i, T c)
  • iを赤に塗るとcの利益を得る。
• penalty_if_blue(int i, T c)
  • iを青に塗るとcの損失になる。
• gain_if_blue(int i, T c)
  • iを青にぬるとcの利益を得る。
• penalty_if_red_blue(int i, int j, T c)
  • iを赤、且つjを青に塗るとcの損失になる。
• penalty_if_different(int i, int j, T c)
  • iとjの色が異なるとcの損失になる。
• must_be_red(int i)
  • iは赤でなければならない。
• must_be_blue(int i)
  • iは青でなければならない。
• if_red_then_must_be_red(int i, int j)
  • iが赤ならば、jは赤でなければならない。
• gain_if_red_red(int i, int j, T c)
  • iとjをともに赤に塗るとcの利益を得る。
• gain_if_blue_blue(int i, int j, T c)
  • iとjをともに青に塗るとcの利益を得る。
• solve()
  • 得られる利益の最大値を返す。

Requirements

• 頂点sは赤に、頂点tは青に塗られる。

Notes

Problems

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

References

• https://kimiyuki.net/blog/2017/12/05/minimum-cut-and-project-selection-problem/
• https://ei1333.github.io/luzhiled/snippets/memo/project-selection.html
• 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

Verified with

• test/aoj/2903/main.test.cpp
• test/aoj/3058/main.test.cpp

Code

#pragma once
#include <cassert>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T, typename Flow>
  class project_selection_problem {
    int N_, s_, t_;
    std::vector<std::tuple<int, int, T>> g_;
    T default_gain_;
    int nodes_;

    constexpr static T INF = std::numeric_limits<T>::max();

  public:
    project_selection_problem() {}
    project_selection_problem(int N) : N_(N), s_(N), t_(N + 1), default_gain_(0), nodes_(N + 2) {}

    void penalty_if_red(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      g_.emplace_back(i, t_, c);
    }

    void gain_if_red(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      default_gain_ += c;
      penalty_if_blue(i, c);
    }

    void penalty_if_blue(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      g_.emplace_back(s_, i, c);
    }

    void gain_if_blue(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      default_gain_ += c;
      penalty_if_red(i, c);
    }

    void penalty_if_red_blue(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      g_.emplace_back(i, j, c);
    }

    void penalty_if_different(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      g_.emplace_back(i, j, c);
      g_.emplace_back(j, i, c);
    }

    void must_be_red(int i) {
      assert(0 <= i and i < N_);
      penalty_if_blue(i, INF);
    }

    void must_be_blue(int i) {
      assert(0 <= i and i < N_);
      penalty_if_red(i, INF);
    }

    void if_red_then_must_be_red(int i, int j) {
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      penalty_if_red_blue(i, j, INF);
    }

    void gain_if_red_red(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      default_gain_ += c;
      int w = nodes_++;

      g_.emplace_back(s_, w, c);
      g_.emplace_back(w, i, INF);
      g_.emplace_back(w, j, INF);
    }

    void gain_if_blue_blue(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      default_gain_ += c;
      int w = nodes_++;

      g_.emplace_back(w, t_, c);
      g_.emplace_back(i, w, INF);
      g_.emplace_back(j, w, INF);
    }

    T solve() {
      Flow flow(nodes_);
      for (auto [i, j, w] : g_) flow.add_edge(i, j, w);
      return default_gain_ - flow.max_flow(s_, t_);
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Graph/project_selection_problem.cpp"
#include <cassert>
#include <limits>
#include <tuple>
#include <utility>
#include <vector>

namespace haar_lib {
  template <typename T, typename Flow>
  class project_selection_problem {
    int N_, s_, t_;
    std::vector<std::tuple<int, int, T>> g_;
    T default_gain_;
    int nodes_;

    constexpr static T INF = std::numeric_limits<T>::max();

  public:
    project_selection_problem() {}
    project_selection_problem(int N) : N_(N), s_(N), t_(N + 1), default_gain_(0), nodes_(N + 2) {}

    void penalty_if_red(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      g_.emplace_back(i, t_, c);
    }

    void gain_if_red(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      default_gain_ += c;
      penalty_if_blue(i, c);
    }

    void penalty_if_blue(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      g_.emplace_back(s_, i, c);
    }

    void gain_if_blue(int i, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      default_gain_ += c;
      penalty_if_red(i, c);
    }

    void penalty_if_red_blue(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      g_.emplace_back(i, j, c);
    }

    void penalty_if_different(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      g_.emplace_back(i, j, c);
      g_.emplace_back(j, i, c);
    }

    void must_be_red(int i) {
      assert(0 <= i and i < N_);
      penalty_if_blue(i, INF);
    }

    void must_be_blue(int i) {
      assert(0 <= i and i < N_);
      penalty_if_red(i, INF);
    }

    void if_red_then_must_be_red(int i, int j) {
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      penalty_if_red_blue(i, j, INF);
    }

    void gain_if_red_red(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      default_gain_ += c;
      int w = nodes_++;

      g_.emplace_back(s_, w, c);
      g_.emplace_back(w, i, INF);
      g_.emplace_back(w, j, INF);
    }

    void gain_if_blue_blue(int i, int j, T c) {
      assert(c >= 0);
      assert(0 <= i and i < N_);
      assert(0 <= j and j < N_);
      default_gain_ += c;
      int w = nodes_++;

      g_.emplace_back(w, t_, c);
      g_.emplace_back(i, w, INF);
      g_.emplace_back(j, w, INF);
    }

    T solve() {
      Flow flow(nodes_);
      for (auto [i, j, w] : g_) flow.add_edge(i, j, w);
      return default_gain_ - flow.max_flow(s_, t_);
    }
  };
}  // namespace haar_lib

Back to top page