Project Selection Problem
(flow/project_selection_problem.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

二値変数 x_i in {0, 1} に対する project selection problem を最大流で解く。 扱えるのは次の形の利益の和の最大化。

• x_i = 1 のとき得る利益
• x_i = 0 のとき得る利益
• x_u = 1, x_v = 0 のとき払う罰金

x_u = 1 -> x_v = 1 の依存制約もこの特別ケースとして表せる。

できること

• ProjectSelectionProblem<T> psp(n) 変数数 n で初期化する
• int add_vertex() 補助変数を 1 つ追加して番号を返す
• void add_true_profit(int v, T x) x_v = 1 のとき利益 x を足す
• void add_false_profit(int v, T x) x_v = 0 のとき利益 x を足す
• void add_penalty(int x, int y, T cost) x_x = 1, x_y = 0 のとき罰金 cost を足す
• void add_if_then(int x, int y) x_x = 1 -> x_y = 1 を課す
• void force_true(int v) x_v = 1 を強制する
• void force_false(int v) x_v = 0 を強制する
• T solve() 最大利益を返す
• const vector<int>& get_selected() const 最適解で x_i = 1 なら 1、そうでなければ 0

使い方

各利益と制約を追加してから solve() を呼ぶ。 行や列、区間などのボーナスを表す補助頂点が必要なら add_vertex() で増やす。

実装上の補足

正の利益を始点側、負の利益を終点側に張り、x=1, y=0 の罰金を x -> y の辺に乗せる最大重み閉包として解く。 get_selected() は最小カット後に始点側へ残った頂点集合を返す。

Depends on

• Dinic法(Dinic) (flow/dinic.cpp)

Verified with

• test/yuki957_project_selection_problem.test.cpp

Code

#include "./dinic.cpp"

template<class T>
class ProjectSelectionProblem {
    int n;
    T base_score{};
    vector<T> weight;
    vector<tuple<int, int, T>> penalty;
    vector<int> selected;

public:
    ProjectSelectionProblem() : n(0) {}
    explicit ProjectSelectionProblem(int n) : n(n), base_score(0), weight(n, 0), selected(n, 0) {}

    int add_vertex() {
        weight.emplace_back(0);
        selected.emplace_back(0);
        return n++;
    }

    int size() const {
        return n;
    }

    void add_true_profit(int v, T x) {
        weight[v] += x;
    }

    void add_false_profit(int v, T x) {
        base_score += x;
        weight[v] -= x;
    }

    void add_penalty(int x, int y, T cost) {
        penalty.emplace_back(x, y, cost);
    }

    void add_if_then(int x, int y) {
        add_penalty(x, y, INF<T>);
    }

    void force_true(int v) {
        add_true_profit(v, INF<T>);
    }

    void force_false(int v) {
        add_false_profit(v, INF<T>);
    }

    T solve() {
        int s = n, t = n + 1;
        Dinic<T, true> mf(n + 2);
        T offset = base_score;
        for (int v = 0; v < n; ++v) {
            if (weight[v] >= 0) {
                offset += weight[v];
                mf.add_edge(s, v, weight[v]);
            } else {
                mf.add_edge(v, t, -weight[v]);
            }
        }
        for (auto&& [x, y, cost] : penalty) {
            mf.add_edge(x, y, cost);
        }
        T cut = mf.flow(s, t);

        fill(selected.begin(), selected.end(), 0);
        queue<int> q;
        q.emplace(s);
        vector<int> vis(n + 2, 0);
        vis[s] = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto&& e : mf.G[v]) {
                if (e.cap <= 0 || vis[e.to]) continue;
                vis[e.to] = 1;
                q.emplace(e.to);
            }
        }
        for (int v = 0; v < n; ++v) {
            selected[v] = vis[v];
        }
        return offset - cut;
    }

    const vector<int>& get_selected() const {
        return selected;
    }
};

/**
 * @brief Project Selection Problem
 */

#line 1 "flow/dinic.cpp"
template<class T, bool directed>
class Dinic {
    void bfs(int s){
        fill(level.begin(),level.end(), -1);
        queue<int> Q;
        level[s] = 0;
        Q.emplace(s);
        while(!Q.empty()){
            int v = Q.front(); Q.pop();
            for (auto &&e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    Q.emplace(e.to);
                }
            }
        }
    }
 
    T dfs(int v, int t, T f){
        if(v == t) return f;
        for(int &i = iter[v]; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                T d = dfs(e.to, t, min(f,  e.cap));
                if(d == 0) continue;
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }
public:
    struct edge {
        int to{}; T cap; int rev{};
        edge() = default;
        edge(int to, T cap, int rev) : to(to), cap(cap), rev(rev) {}
    };
 
    vector<vector<edge>> G;
    vector<int> level, iter;
    Dinic() = default;
    explicit Dinic(int n) : G(n), level(n), iter(n) {}
 
    void add_edge(int from, int to, T cap){
        G[from].emplace_back(to, cap, G[to].size());
        G[to].emplace_back(from, directed ? 0 : cap,  G[from].size()-1);
    }
 
 
    T flow(int s, int t, T lim = INF<T>){
        T ret = 0;
        while(true) {
            bfs(s);
            if(level[t] < 0 || lim == 0) break;
            fill(iter.begin(),iter.end(), 0);
            while(true){
                T f = dfs(s, t, lim);
                if(f == 0) break;
                ret += f;
                lim -= f;
            }
        }
        return ret;
    }
};

/**
 * @brief Dinic法(Dinic)
 */
#line 2 "flow/project_selection_problem.cpp"

template<class T>
class ProjectSelectionProblem {
    int n;
    T base_score{};
    vector<T> weight;
    vector<tuple<int, int, T>> penalty;
    vector<int> selected;

public:
    ProjectSelectionProblem() : n(0) {}
    explicit ProjectSelectionProblem(int n) : n(n), base_score(0), weight(n, 0), selected(n, 0) {}

    int add_vertex() {
        weight.emplace_back(0);
        selected.emplace_back(0);
        return n++;
    }

    int size() const {
        return n;
    }

    void add_true_profit(int v, T x) {
        weight[v] += x;
    }

    void add_false_profit(int v, T x) {
        base_score += x;
        weight[v] -= x;
    }

    void add_penalty(int x, int y, T cost) {
        penalty.emplace_back(x, y, cost);
    }

    void add_if_then(int x, int y) {
        add_penalty(x, y, INF<T>);
    }

    void force_true(int v) {
        add_true_profit(v, INF<T>);
    }

    void force_false(int v) {
        add_false_profit(v, INF<T>);
    }

    T solve() {
        int s = n, t = n + 1;
        Dinic<T, true> mf(n + 2);
        T offset = base_score;
        for (int v = 0; v < n; ++v) {
            if (weight[v] >= 0) {
                offset += weight[v];
                mf.add_edge(s, v, weight[v]);
            } else {
                mf.add_edge(v, t, -weight[v]);
            }
        }
        for (auto&& [x, y, cost] : penalty) {
            mf.add_edge(x, y, cost);
        }
        T cut = mf.flow(s, t);

        fill(selected.begin(), selected.end(), 0);
        queue<int> q;
        q.emplace(s);
        vector<int> vis(n + 2, 0);
        vis[s] = 1;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto&& e : mf.G[v]) {
                if (e.cap <= 0 || vis[e.to]) continue;
                vis[e.to] = 1;
                q.emplace(e.to);
            }
        }
        for (int v = 0; v < n; ++v) {
            selected[v] = vis[v];
        }
        return offset - cut;
    }

    const vector<int>& get_selected() const {
        return selected;
    }
};

/**
 * @brief Project Selection Problem
 */

Back to top page