燃やす埋める
(graph/maximumflow/moyasu_umeru.hpp)

• View this file on GitHub
• Last update: 2020-09-13 19:13:22+09:00
• Include: #include "graph/maximumflow/moyasu_umeru.hpp"
• Link: https://yosupo.hatenablog.com/entry/2015/03/31/134336

概要

わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテク

条件を読ませて, 張るべき辺を返す.

使用例

• moyasu_umeru<int> mu(V) : $V$頂点のグラフを定義.
  • コストの型 : int
• mu.red_blue_penalty(r, b, pena) : 頂点$r$を赤く, 頂点$b$を青く塗ったら罰金$pena$.
• mu.red_penalty(r, pena) : 頂点$r$を赤く塗ったら罰金$pena$.
• mu.blue_penalty(b, pena) : 頂点$b$を赤く塗ったら罰金$pena$.
• mu.red_reward(r, rwrd) : 頂点$r$を赤く塗ったら賞金$rwrd$.
• mu.blue_reward(b, rwrd) : 頂点$b$を青く塗ったら賞金$rwrd$.
• mu.reds_reward(v_r, rwrd) : 頂点群$v_r$を全て赤く塗ったら賞金$rwrd$.
• mu.blues_reward(v_b, rwrd) : 頂点群$v_b$を青て赤く塗ったら賞金$rwrd$.
• mu.edges : 張るべき辺.
• mu.margin : 無条件で得られる賞金.

Code

/**
* @brief 燃やす埋める
* @docs docs/graph/maximumflow/moyasu_umeru.md
* @see https://yosupo.hatenablog.com/entry/2015/03/31/134336
*/

template <typename T>
struct moyasu_umeru {
    int N;
    T margin;
    const int R, B;  // R:red, B:blue
    const T INF;
    vector<tuple<int, int, T>> edges;
    moyasu_umeru(int V, T INF = numeric_limits<T>::max() / 10)
        : N(V + 2), margin(0), R(V), B(V + 1), INF(INF) {}
    void red_blue_penalty(int r, int b, T pena) {
        edges.emplace_back(r, b, pena);
    }
    void red_penalty(int r, T pena) {
        red_blue_penalty(r, B, pena);
    }
    void blue_penalty(int b, T pena) {
        red_blue_penalty(R, b, pena);
    }
    void red_reward(int r, T rwrd) {
        margin += rwrd;
        blue_penalty(r, rwrd);
    }
    void blue_reward(int b, T rwrd) {
        margin += rwrd;
        red_penalty(b, rwrd);
    }
    void reds_reward(vector<int> v_r, T rwrd) {
        margin += rwrd;
        edges.emplace_back(R, N, rwrd);
        for (auto& r : v_r) edges.emplace_back(N, r, INF);
        ++N;
    }
    void blues_reward(vector<int> v_b, T rwrd) {
        margin += rwrd;
        edges.emplace_back(N, B, rwrd);
        for (auto& b : v_b) edges.emplace_back(b, N, INF);
        ++N;
    }
};

#line 1 "graph/maximumflow/moyasu_umeru.hpp"
/**
* @brief 燃やす埋める
* @docs docs/graph/maximumflow/moyasu_umeru.md
* @see https://yosupo.hatenablog.com/entry/2015/03/31/134336
*/

template <typename T>
struct moyasu_umeru {
    int N;
    T margin;
    const int R, B;  // R:red, B:blue
    const T INF;
    vector<tuple<int, int, T>> edges;
    moyasu_umeru(int V, T INF = numeric_limits<T>::max() / 10)
        : N(V + 2), margin(0), R(V), B(V + 1), INF(INF) {}
    void red_blue_penalty(int r, int b, T pena) {
        edges.emplace_back(r, b, pena);
    }
    void red_penalty(int r, T pena) {
        red_blue_penalty(r, B, pena);
    }
    void blue_penalty(int b, T pena) {
        red_blue_penalty(R, b, pena);
    }
    void red_reward(int r, T rwrd) {
        margin += rwrd;
        blue_penalty(r, rwrd);
    }
    void blue_reward(int b, T rwrd) {
        margin += rwrd;
        red_penalty(b, rwrd);
    }
    void reds_reward(vector<int> v_r, T rwrd) {
        margin += rwrd;
        edges.emplace_back(R, N, rwrd);
        for (auto& r : v_r) edges.emplace_back(N, r, INF);
        ++N;
    }
    void blues_reward(vector<int> v_b, T rwrd) {
        margin += rwrd;
        edges.emplace_back(N, B, rwrd);
        for (auto& b : v_b) edges.emplace_back(b, N, INF);
        ++N;
    }
};

Back to top page