ネットワークフロー理論における「最小カット問題」の考え方・応用例を総整理！

Last updated at 2026-09-03Posted at 2026-09-02

お久しぶりです！
NTT データ数理システムで顧問をしている大槻（けんちょん）です。好きなアルゴリズムは最小カットです。

今回は「$i$ 番目を選ぶならば $j$ 番目も選ばないとペナルティを与える」のような、要素間の相互作用¹を伴う一見扱いづらい制約条件を大量に含む最適化問題について解説します。この最適化問題は、ネットワークフロー理論における最小カット問題と等価であることをみていきます。絶大な表現力を有しており、多数の問題がこれに帰着できます。

なお本記事は、最小カット問題についての導入を入念に行なった上で、次の 2 本の記事（参考文献 [1][2]）の内容を取り込んだものともいえます。これら 2 本の記事の内容に対して、豊富な問題例を示すことも大きな目的です。

theory_and_me: 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その②
noshi: 最小カット問題の k 値への一般化

また、行間を丁寧に書いたため、AtCoder 水色以上の力があれば最後まで読めると思います。最小カット問題の深淵が普及して、有志コンなどでオリジナリティ溢れる問題がたくさん作られるようになると嬉しいです。

1: （★☆☆☆☆）最小カット問題
ㅤㅤ1-1: 最小カット問題とは
ㅤㅤ1-2: カットについてのよくある誤解 --- 「削除する辺の集合」ではない！
ㅤㅤ1-3: 最小カット問題の考え方の比較 --- 頂点集合の分割か、辺の削除か
ㅤㅤ1-4: 最小カットを求める方法
2: （★☆☆☆☆）最小カットは何を表すのか (1)：耐故障性
3: （★☆☆☆☆）最小カットは何を表すのか (2)：プロジェクト選択
ㅤㅤ3-1: カットを「プロジェクト選択」と解釈する
ㅤㅤ3-2: プロジェクト選択問題
ㅤㅤ3-3: プロジェクト選択問題を「辺の削除」で捉えると......
ㅤㅤ3-4: Historical Remark --- 露天掘り問題とプロジェクト選択問題
4: （★☆☆☆☆）燃やす埋める問題
ㅤㅤ4-1: 燃やす埋める問題とは
ㅤㅤ4-2: Historical Remark --- 競プロでの燃やす埋める
5: （★★☆☆☆）プロジェクト選択問題の拡張 --- コストが負の場合など
ㅤㅤ5-1: Ai < 0 や Bi < 0 もあり得る場合
ㅤㅤ5-2: プロジェクト u, v をともに選択する → 利得
ㅤㅤ5-3: K 個のプロジェクトをすべて選択する → 利得
6: （★★☆☆☆）問題演習 Part. 1　
ㅤㅤ6-1: 最小カット問題への帰着の思いつき方
ㅤㅤ6-2: 簡単な問題（NoviSteps 3D 相当）
ㅤㅤ6-3: 少し難しい問題（NoviSteps 4D 相当）
ㅤㅤ6-4: 現実世界への応用例

後編（予告）

7: （★★★☆☆）2 変数劣モジュラ関数のグラフ表現
8: （★★★☆☆）ビット反転
9: （★★★☆☆）問題演習 Part. 2
10: （★★★★☆）K 値への拡張
11: （★★★★★）Monge 関数のグラフ表現
12: （★★★★★）3 変数劣モジュラ関数のグラフ表現
13: （★★★★★）問題演習 Part. 3

ㅤ

1：最小カット問題

まず、最小カット問題について解説します。

1-1：最小カット問題とは

たとえば、次のグラフを考えます。2 つの頂点 $s, t$ が指定されています。

このグラフ上で、頂点 $s$ を含むようにいくつかの頂点を選びます（選ぶ頂点の集合を $S$ とします）。ただし、$S$ が頂点 $t$ を含まないようにします。また、選ばなかった頂点の集合を $T$ とします。このとき、集合 $T$ は頂点 $t$ を含みます。そして、「$S$ 側から $T$ 側へと出ていく辺の本数」を数えます。

たとえば、下図は、青色で示した頂点を選んだ様子を示しています。$S$ 側から $T$ 側へと出ていく辺の本数は、赤太線で示した 5 本です。なお、下図の頂点 $b$ から頂点 $a$ へと向かう辺はカウントしないことに注意しましょう。この辺は、頂点 $S$ から出ていく辺ではなく、頂点 $S$ に入っていく辺であるためです。

最小カット問題とは、頂点の集合 $S$ を適切に選ぶことで、「$S$ 側から $T$ 側へと出ていく辺の本数」を最小化する問題です。なお、グラフの頂点集合の分割 $(S, T)$ を、カットと呼びます。また、$S$ 側から $T$ 側へと出ていく辺の集合をカット $(S, T)$ に関するカットセットと呼びます。さらに本記事では、カットセットに含まれる辺の本数を、カット $(S, T)$ の重みと呼ぶことにします³。この定義を用いると、最小カット問題とは、「重みが最小のカットを求める問題」です。

問題 1：最小カット問題（重み無し）

有向グラフと 2 頂点 $s, t$ が与えられる。グラフの頂点集合を、$s$ を含む頂点集合 $S$ と $t$ を含む頂点集合 $T$ へと分割する。

始点が $S$ に属し、終点が $T$ に属するような辺の本数（カット $(S, T)$ の重み）が最小となる分割を求めよ。

上のグラフの場合、最小カットは下図の通りです。$S$ 側から $T$ 側へと出ていく辺の本数は 3 本です。

また、辺に重みがあるバージョンを考えることもできます。その場合の最小カット問題は、$S$ 側から $T$ 側へと出ていく辺の重みの総和が最小のカット $(S, T)$ を求める問題となります。また、この総和をカット $(S, T)$ の重みと呼ぶことにします。

問題 2：最小カット問題（重み付き）

辺に重みのついた有向グラフと 2 頂点 $s, t$ が与えられる（重みは非負）。グラフの頂点集合を、$s$ を含む頂点集合 $S$ と $t$ を含む頂点集合 $T$ へと分割する。

始点が $S$ に属し、終点が $T$ に属するような辺の重みの総和（カット $(S, T)$ の重み）が最小となる分割を求めよ。

なお、グラフの頂点の個数を $N + 2$（$s, t$ を除いて $N$ 個）とすると、カットは $2^N$ 通りあります。なぜならば、$s, t$ を除く $N$ 個の頂点について、「$S$ 側に含めるか」「$T$ 側に含めるか」の 2 通りずつの選択肢があるからです。

1-2：カットについてのよくある誤解 --- 「削除する辺の集合」ではない！

上でみたように、カットは頂点についての定義、カットセットは辺についての定義であることに注意しましょう⁴。カットに対して、その字面に対する印象から、取り除くことで $s$ から $t$ へと到達不能にする辺の集合のことである......という誤解は非常によくみられます。そもそも、カットは頂点についての定義なのです⁵。

このような誤解が生まれる背景としては、「取り除くことで $s$ から $t$ へ到達不能にする辺の重みの総和の最小値」を求める問題が、最小カットによって解ける最初の例題として、よく取り上げられることが一因だと思います⁶。

問題 3：最小コストグラフ破壊問題

辺に重みのついた有向グラフと 2 頂点 $s, t$ が与えられる（重みは非負）。

今、いくつかの辺を取り除くことによって、頂点 $s$ から頂点 $t$ へと到達できないようにしたい。取り除く辺の重みの総和の最小値を求めよ。

この問題の解は、最小カット問題の最適解から構成することができます。たとえば、上の「問題 2: 最小カット問題（重み付き）」で例示したグラフにおいて、赤太線の辺を削除すると、下図のようになります。$s$ から $t$ へと到達不能となることが分かります。一般に、最小カット問題の最適解（最適カット）についてのカットセットが、問題 3 の最適解にもなります⁷。

補足すると、下図のような包含関係が成り立ちます。カット $(S, T)$ に関するカットセット（$S$ 側から $T$ 側へと出ていく辺の集合）は、一般に、「取り除くことで $s$ から $t$ へ到達不能になる」という性質を満たします。逆に、取り除くことで $s$ から $t$ へ到達不能になるような辺の集合は、カットセットになるとは限りません。

たとえば、下図の赤太線で示す辺の集合は、「取り除くことで $s$ から $t$ へ到達不能になる」という性質を満たしますが、カットセットにはなりません。

それでも、

(カットセットの重みの最小値) = ($s$ から $t$ へ到達不能になるように取り除く辺の重みの最小値)

となるのです。一般に、最適化問題を解くとき「考察対象を狭めても、その中に最適解が含まれる」ことを示すのが有効なケースは多々あります。最小カット問題についても、カットセットの重みの最小値を求める問題と定式化されることが多いです。

1-３：最小カット問題の考え方の比較 --- 頂点集合の分割か、辺の削除か

ここまで、最小カット問題について、2 つの考え方があることをみました。

考え方 (1)：カットセットに含まれる辺の重みの総和が最小となるように、頂点集合の分割の仕方を最適化する問題
考え方 (2)：グラフの辺を削除することで、$s$ から $t$ へと到達不能にする問題

初学者にとっては (2) の考え方が分かりやすいと思えるかもしれません。(2) の考え方で最小カットの解説をしている資料としては、たとえば次のものがあります。競技プログラミング界で、最小カット問題の普及に大きく貢献したスライドです。

nico_shindannin: 最小カットを使って「燃やす埋める問題」を解く

しかしながら、「$s$ から $t$ へと到達不能にする」という条件は、数学的に扱いづらいですし、問題が複雑になればなるほど頭が混乱しやすくなります。

たとえば、下図のように、取り止めもなくバラバラに辺を削除するようなものも考慮対象となってしまいます。このような訳分からないものは、良い性質をもつことをあまり期待できず、扱いづらいことは想像に難くないでしょう。また、人間がグラフをかいて問題を解くとき、取り除くことで $s$ から $t$ へ到達不能になるのかを目視で確認することも困難です。最終的には、頂点集合の分割の考え方に慣れていくのがよいと思います。

一方、カットを「頂点集合の分割 $(S, T)$」であると定義した上で、カットセットを「$S$ 側から $T$ 側へと出ていく辺の集合」と定義すると、良い性質をもつようになり、扱いやすくなります。たとえば、カット $(S, T)$ の重みを $f(S)$ とすると、$f$ は劣モジュラ関数となります（後編で述べます）。

また、どのような分割 $(S, T)$ を考えても、そのカットセットが「削除すると $s$-$t$ 間を分断できる」という性質を満たすという点も気持ちがよいです。この点は、問題の解きやすさにも直結します。

最小カット問題は、「頂点集合の分割の仕方」を最適化する問題と考えるとよい

1-4：最小カットを求める方法

最小カットを求める方法としては、Dinic 法が有名です。頂点数 $V$、辺数 $E$ のグラフの最小カットを $O(V^2E)$ の計算量で求めることができます。下のコードは、Dinic 法の実装と、その使用例（下図のグラフに対して最小カットを求めるもの）を示しています。

Dinic 法

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cassert>
using namespace std;


// edge class
template<class FLOW> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOW cap, icap, flow;
    
    // constructor
    constexpr FlowEdge() noexcept = default;
    constexpr FlowEdge(int rev, int from, int to, FLOW cap, FLOW rcap = 0) 
        : rev(rev), from(from), to(to), cap(cap), icap(cap), flow(rcap) {
    }
};

// graph class
template<class FLOW> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOW>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.clear(), list.resize(n);
        pos.clear();
    }
    void clear() {
        list.clear(), pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOW>> &operator [] (int i) {
        assert(0 <= i && i < (int)list.size());
        return list[i];
    }
    const vector<FlowEdge<FLOW>> &operator [] (int i) const {
        assert(0 <= i && i < (int)list.size());
        return list[i];
    }
    size_t size() const noexcept {
        return list.size();
    }
    size_t size_edegs() const noexcept {
        return pos.size();
    }
    FlowEdge<FLOW> &get_rev_edge(const FlowEdge<FLOW> &e) {
        return list[e.to][e.rev];
    }
    const FlowEdge<FLOW> &get_rev_edge(const FlowEdge<FLOW> &e) const {
        return list[e.to][e.rev];
    }
    
    // add_edge
    void add_edge(int from, int to, FLOW cap, FLOW rcap = 0) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        int from_id = int(list[from].size()), to_id = int(list[to].size());
        if (from == to) to_id++;
        pos.emplace_back(from, from_id);
        list[from].push_back(FlowEdge<FLOW>(to_id, from, to, cap, rcap));
        list[to].push_back(FlowEdge<FLOW>(from_id, to, from, rcap, cap));
    }
    void add_bidirected_edge(int from, int to, FLOW cap) {
        assert(0 <= from && from < (int)list.size() && 0 <= to && to < (int)list.size());
        assert(cap >= 0);
        add_edge(from, to, cap, cap);
    }

    // 最小カットを復元する
    // 1: S に入れるもの, -1: T に入れるもの, 0: S, T のどちらかに入れるとよいもの
    vector<int> find_cut(int s, int t) const {
        vector<int> res(size(), 0);
        auto dfs_s = [&](auto &&dfs_s, int v) -> void {
            res[v] = 1;
            for (const auto &e : list[v]) {
                if (res[e.to] || e.cap <= 0) continue;
                dfs_s(dfs_s, e.to);
            }
        };
        auto dfs_t = [&](auto &&dfs_t, int v) -> void {
            res[v] = -1;
            for (const auto &e : list[v]) {
                auto re = get_rev_edge(e);
                if (res[e.to] || re.cap <= 0) continue;
                dfs_t(dfs_t, e.to);
            }
        };
        dfs_s(dfs_s, s), dfs_t(dfs_t, t);
        return res;
    }
};

// Dinic
template<class FLOW> FLOW Dinic(FlowGraph<FLOW> &G, int s, int t, FLOW limit_flow) {
    assert(0 <= s && s < (int)G.size() && 0 <= t && t < (int)G.size() && s != t);
    FLOW current_flow = 0;
    vector<int> level((int)G.size(), -1), iter((int)G.size(), 0);
    
    // Dinic BFS
    auto bfs = [&]() -> void {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (const FlowEdge<FLOW> &e : G[v]) {
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        }
    };
    
    // Dinic DFS
    auto dfs = [&](auto self, int v, FLOW up_flow) {
        if (v == t) return up_flow;
        FLOW res_flow = 0;
        for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
            FlowEdge<FLOW> &e = G[v][i], &re = G.get_rev_edge(e);
            if (level[v] >= level[e.to] || e.cap <= 0) continue;
            FLOW flow = self(self, e.to, min(up_flow - res_flow, e.cap));
            if (flow <= 0) continue;
            res_flow += flow;
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
            if (res_flow == up_flow) break;
        }
        return res_flow;
    };
    
    // flow
    while (current_flow < limit_flow) {
        bfs();
        if (level[t] < 0) break;
        iter.assign((int)iter.size(), 0);
        while (current_flow < limit_flow) {
            FLOW flow = dfs(dfs, s, limit_flow - current_flow);
            if (flow <= 0) break;
            current_flow += flow;
        }
    }
    return current_flow;
};

template<class FLOW> FLOW Dinic(FlowGraph<FLOW> &G, int s, int t) {
    return Dinic(G, s, t, numeric_limits<FLOW>::max());
}


//------------------------------//
// Examples
//------------------------------//

int main() {
    // グラフの入力（Qiita にかいた例）
    int V = 5, E = 6, s = 0, t = 4;  // 頂点 s, t の番号をそれぞれ 0, 4 とする
    FlowGraph<int> G(V);
    G.add_edge(1, t, 50);
    G.add_edge(s, 2, 7);
    G.add_edge(s, 3, 40);
    G.add_edge(3, t, 4);
    G.add_edge(1, 2, 100);
    G.add_edge(3, 1, 1000);

    // 最大流を流す (最小カットと値が一致する）
    int min_cut = Dinic(G, s, t);

    // カット (S, T) を求める
    // 1: S に入れるもの, -1: T に入れるもの, 0: S, T のどちらかに入れるとよいもの
    vector<int> cut = G.find_cut(s, t);

    // 出力
    cout << "min_cut: " << min_cut << endl;
    for (int v = 0; v < V; v++) {
        cout << "node " << v << ": " << (cut[v] == 1 ? "S-side" : "T-side") << endl;
    }
}

Dinic 法の詳細については、本記事では解説しませんが、参考文献 [11] などで解説されていますのでぜひ読んでみてください。他にも、Dinic 法よりも基本的な解法である Ford-Fulkerson 法については、参考文献 [3][4][5] でも解説されています。無料で読める資料としては、たとえば以下の記事があります。

うさぎでもわかる離散数学（グラフ理論）　第15羽　最大フロー・最小カットの求め方

また、AtCoder では Dinic 法を実装したライブラリ（このページの #include <atcoder/mincostflow>）が無料で提供されています。

これらのライブラリを用いることで、本記事で紹介する問題をすべて解くことができます。なお、本記事ではこれ以降、問題の解法を示す際に計算量については言及せず、最小カット問題に帰着できたならば「解けた」とみなすこととします。

2：最小カットは何を表すのか (1)：耐故障性

最小カットの重みは、$s$-$t$ 間の耐故障性を表していると解釈できます。上述の通り、最小カットの重みは、$s$ から $t$ へ到達不能にするための最小コストに一致します。

最小カットの重みが 11 であることは、グラフに対して 11 未満のコストでどのように損傷を与えても、$s$-$t$ 間の連結性が保たれることを意味します。このように、最小カット問題（とその双対の最大流問題）は、ネットワークの耐故障性を評価する重要な指標を与える問題であるとして、古くからさまざまな界隈で研究されてきました。

ㅤ

3：最小カットは何を表すのか (2)：プロジェクト選択

さて、いよいよ最小カットが何を表すのか --- その深淵を覗きに行きます。最小カット問題は、頂点集合の分割の仕方を最適化する問題であると散々述べました。この「分割」に意味を与えていきます。

3-1：カットを「プロジェクト選択」と解釈する

ここでは、グラフの頂点はプロジェクト（実行に移すかどうかを選択しようとしているもの）を表すとします。そして、グラフのカットと、プロジェクト選択とが 1 対 1 に対応する状況を考えます。つまり、

$S$ 側に含まれる頂点に対応するプロジェクトは、選択する
$T$ 側に含まれる頂点に対応するプロジェクトは、選択しない

とします。

たとえば、プロジェクト 1, 2, 3 があるとして、それに対応するグラフが下図の通りであるとします。このグラフを、プロジェクト選択の言葉で、どのように解釈できるかを考えてみましょう。

結論からいうと、このグラフは、プロジェクト選択の言葉で次のように解釈できます。

【プロジェクト選択のコスト条件】

条件 A：プロジェクト 1 を選択すると、50 のコストがかかる
条件 B：プロジェクト 2 を選択しないと、7 のコストがかかる
条件 C：プロジェクト 3 を選択すると 4 のコストがかかり、選択しないと 40 のコストがかかる
条件 D：「プロジェクト 1 を選択して、プロジェクト 2 を選択しない」ことにすると、100 のコストがかかる
条件 E：「プロジェクト 3 を選択して、プロジェクト 1 を選択しない」ことにすると、1000 のコストがかかる

つまり、「上図のグラフの最小カットを求める」ことと、「上のコスト条件下で総コストが最小となるプロジェクト選択をすること」は、全く同じということです。このあと詳しく解説します。

なお、具体的な最適解は、上図に示す（これ以降、カットを図示するときに $T$ は示さず $S$ のみ示すようにします）ように、$S =$ {$s, 2$}, $T =$ {$t, 1, 3$} というカット（カットの重みは 40）であり、

プロジェクト 1 を選択しない
プロジェクト 2 を選択する
プロジェクト 3 を選択しない

というプロジェクト選択（最小コストは 40）です。

条件 A: プロジェクト 1 を選択すると 50 のコスト

それでは、プロジェクト選択のコスト条件を 1 つずつ検討します。まず、条件 A「プロジェクト 1 を選択すると 50 のコスト」について考えます。このコスト条件は、グラフの辺 $(1, t)$ に対応します。みやすいように、辺 $(1, t)$ のみを取り出して考えてみましょう。

カット $(S, T)$ としてあり得るものは $2^3 = 8$ 通りあります。それらを下図にすべて示しました。よく観察すると、

頂点 1 を $S$ 側に含めると、カットセットが辺 $(1, t)$ を含むので、カットの重みに 50 が加算される
頂点 1 を $T$ 側に含めると、カットセットが辺 $(1, t)$ を含まないので、カットの重みは加算されない

ということが分かります。このことを、プロジェクト選択の言葉でいうと

プロジェクト 1 を選択すると、50 のコストがかかる
プロジェクト 1 を選択しないと、コストはかからない

となります。

条件 B: プロジェクト 2 を選択しないと 7 のコスト

次に、条件 B「プロジェクト 2 を選択しないと 7 のコスト」を考えます。この条件は、グラフの辺 $(s, 2)$ に対応します。条件 A と同様に考えることで、

頂点 2 を $S$ 側に含めると、カットセットが辺 $(s, 2)$ を含まないので、カットの重みは加算されない
頂点 2 を $T$ 側に含めると、カットセットが辺 $(s, 2)$ を含むので、カットの重みに 7 が加算される

ということが分かります。このことを、プロジェクト選択の言葉でいうと

プロジェクト 2 を選択すると、コストはかからない
プロジェクト 2 を選択しないと、7 のコストがかかる

となります。

条件 C: プロジェクト 3 を選択すると 4 のコスト、選択しないと 40 のコスト

さらに、条件 C「プロジェクト 3 を選択すると 4 のコスト、選択しないと 40 のコスト」を考えます。この条件は、グラフの 2 本の辺 $(s, 3)$, $(3, t)$ に対応します。条件 A, B と同様に考えることで、

頂点 3 を $S$ 側に含めると、カットセットが辺 $(3, t)$ を含むので、カットの重みに 4 が加算される
頂点 3 を $T$ 側に含めると、カットセットが辺 $(s, 3)$ を含むので、カットの重みに 40 が加算される

ということが分かります。このことを、プロジェクト選択の言葉でいうと

プロジェクト 3 を選択すると、4 のコストがかかる
プロジェクト 3 を選択しないと、40 のコストがかかる

となります。

条件 D: 「プロジェクト 1 を選択して、プロジェクト 2 を選択しない」ことにすると、100 のコスト

条件 A〜C は単一のプロジェクトの選択に関するものでしたが、この条件 D は 2 つのプロジェクト 1, 2 の相互作用に関するものです。グラフの辺 (1, 2) に対応します。次の 4 つの場合に分けて考えてみましょう。

頂点 1 も頂点 2 も $S$ に含まれる場合
頂点 1 は $S$ に含まれて、頂点 2 は $S$ に含まれない場合
頂点 1 は $S$ に含まれず、頂点 2 は $S$ に含まれる場合
頂点 1 も頂点 2 も $S$ に含まれない場合

下図に示す通り、辺 (1, 2) をカットセットに含むのは「頂点 1 は $S$ に含まれて、頂点 2 は $S$ に含まれない場合」のみです。なお、下図の例はすべて頂点 3 が $S$ に含まれる場合を示していますが、頂点 3 が $S$ に含まれない場合も同様です。

このことを、プロジェクト選択の言葉でいうと

「プロジェクト 1 を選択して、プロジェクト 2 を選択しない」ことにすると、100 のコストがかかる

となります。

条件 E: 「プロジェクト 3 を選択して、プロジェクト 1 を選択しない」ことにすると、1000 のコスト

この条件 E は、グラフの辺 (3, 1) に対応します。D と同様ですので、ぜひ絵をかいて考えてみてください。結論をいうと、辺 (3, 1) をカットセットに含むのは「頂点 3 は $S$ に含まれて、頂点 1 は $S$ に含まれない」ときです。

プロジェクト選択の言葉でいうと

「プロジェクト 3 を選択して、プロジェクト 1 を選択しない」ことにすると、1000 のコストがかかる

となります。

3-2：プロジェクト選択問題

ここまで、グラフの「カット」とプロジェクトの「選択」とを 1 対 1 に対応させた上で、グラフの辺の重みが次のように解釈できることをみてきました。

辺の重み	プロジェクト選択での解釈
始点が $s$ である辺 $(s, v)$ の重み	プロジェクト $v$ を選択しないときのコスト
終点が $t$ である辺 $(v, t)$ の重み	プロジェクト $v$ を選択するときのコスト
始点も終点も $s$ や $t$ ではない辺 $(u, v)$ の重み	プロジェクト $u$ を選択してプロジェクト $v$ を選択しないときのコスト

これを踏まえると、次のプロジェクト選択問題（Project Selection Problem）は最小カット問題そのものであることが分かります。

問題 4：プロジェクト選択問題（Project Selection Problem）

$N$ 個のプロジェクト $1, 2, \dots, N$ があり、どのプロジェクトを実行するかを選択したいとする。

プロジェクト $i$ を選択すると、$A_i$ ($\geq$ 0) だけコストがかかる
プロジェクト $i$ を選択しないと、$B_i$ ($\geq$ 0) だけコストがかかる

また、$M$ 個の条件がある。条件 $j$ は、次のものである。

プロジェクト $U_j$ を選択して、プロジェクト $V_j$ を選択しないとき、ペナルティとして $C_j$ ($\geq$ 0) だけコストがかかる

実行するプロジェクトを最適に選択するときの、コストの総和の最小値を求めよ。

このプロジェクト選択問題の最適解は、次のグラフの最小カットに一致します。

頂点 $1, 2, \dots, N$ および、頂点 $s, t$ からなる頂点数 $N+2$ のグラフを考える
頂点 $s$ から頂点 $i$ へ、重み $B_i$ の辺を張る（$i = 1, 2, \dots, N$）
- $B_i = 0$ の場合は張らなくてよい
頂点 $i$ から頂点 $t$ へ、重み $A_i$ の辺を張る（$i = 1, 2, \dots, N$）
- $A_i = 0$ の場合は張らなくてよい
頂点 $U_j$ から頂点 $V_j$ へ、重み $C_j$ の辺を張る（$j = 1, 2, \dots, M$）

なお、

「プロジェクト $U_j$ を選択するならば、プロジェクト $V_j$ も選択しなければならない」

という形の条件を考えることもあります。その場合は、$C_j = \infty$ とすればよいです。つまり、頂点 $U_j$ から頂点 $V_j$ へ、重み $\infty$ の辺を張ればよいです。

3-3：プロジェクト選択問題を「辺の削除」で捉えると......

本記事は、プロジェクト選択はあくまで「頂点集合の分割」として捉えるのがよいという立場をとっています。しかしながら、「辺の削除」として捉えたときの解釈をみておくと理解が深まると思います。

「辺の削除」解釈の下では、下図のように、

$s$ と接続する辺 $(s, v)$ の重みを「プロジェクト $v$ を選択しないときのコスト」
$t$ と接続する辺 $(v, t)$ の重みを「プロジェクト $v$ を選択するときのコスト」

と捉えます。そして、辺を取り除くことで $s$ から $t$ へ到達不能にするための最小コストを求めるものと考えます。

この解釈の下では、たとえば辺 $(3, 1)$ は、

辺 $(1, t)$ と辺 $(s, 3)$ が両方とも取り除かれない場合には、辺 $(3, 1)$ を取り除かないと $s$-$t$ 間が繋がってしまうこと

を表します。つまり、

プロジェクト 1 を選択して、プロジェクト 3 を選択しないと、1000 のペナルティがかかること

を表現していると捉えることができます。

3-4: Historical Remark --- 露天掘り問題とプロジェクト選択問題

歴史的には 1960 年代を通して、露天堀り問題（Open-pit Mining Problem）が盛んに研究されていました（Lerchs and Grossmann, 1965 [7] など）。露天掘り問題では、鉱床を 3 次元のブロックに分割し、各ブロック $i$ は

$$ w_i= \text{鉱石価値}-\text{採掘費用} $$

によって定められる価値をもつとします。鉱石であれば $w_i > 0$、廃石であれば $w_i < 0$ になることがあります。しかし、地下深くの価値あるブロックだけを突然掘ることはできません。斜面の安定性のため、あるブロックを掘るためにはその上にあるブロックも掘らなければならない......といった条件を考慮する必要があります。この条件は、まさにプロジェクト選択問題（Project Selection Problem）でも扱っているものですね。

一方、プロジェクト選択問題は、露天堀り問題とは独立に、1970 年前後に盛んに研究されていました（Rhys, 1970 [8] など）。その後、Picard, 1976 [9] は、露天掘り問題とプロジェクト選択問題を統合する形で抽象化して、ネットワークフロー理論の一部として綺麗に整理しました。

こうした歴史的な流れは、Hochbaum, 2004 [10] にまとめられています。関心のある方はぜひ読んでみてください。

4：燃やす埋める問題

いよいよ、燃やす埋める問題についてみていきます。

4-1：燃やす埋める問題とは

皆が「燃やす埋める」と呼んでいる問題群の起源を下に示します。Komaki さんが自身の記事中で提唱した問題です⁸。まさに、プロジェクト選択問題と同じものですね。

Komaki さん自身がこれを「燃やす埋める」問題と名付けたわけではありませんが、その問題設定のインパクトの強さから、いつしか「燃やす埋める」問題と呼ばれるようになりました。また、各頂点を「燃やす」「埋める」という 2 択に分けるテクニックのことを「燃やす埋める」と呼ぶ文化が生まれました。

問題 5：燃やす埋める問題（元ネタ）

$N$ 個のゴミがある。各ゴミに対して、燃やすか、埋めるかを選択する。

ゴミ $i$ を燃やすのには、$A_i$ ($\geq$ 0) 円のコストがかかる
ゴミ $i$ を埋めるのには、$B_i$ ($\geq$ 0) 円のコストがかかる

ただし、$M$ 個の制約条件がある。制約条件 $j$ は、次のものである。

ゴミ $U_j$ を燃やして、ゴミ $V_j$ を埋めるとき、ペナルティとして $C_j$ ($\geq$ 0) 円のコストがかかる

すべてのゴミを燃やすか埋めるかをするためのコストの総和の最小値を求めよ。

燃やす埋めるというネーミングの是非について

ここで、改めて「燃やす埋める」というネーミングの是非を議論してみたいと思います。個人的には、問題を指す言葉としての「燃やす埋める」には肯定的、テクニックを指す言葉としての「燃やす埋める」には否定的な立場をとっています。たとえば、「この問題は燃やす埋めるですね」という言い方には肯定的、「この問題は燃やす埋めるで解けます」という言い方には否定的な立場をとっています。

問題を指す語「燃やす埋める」に対しては、確かに「プロジェクト選択問題」という、より広く世界に受け入れられている名称が存在することには注意が必要です。しかしながら、「燃やす埋める」という名称の Google 検索性の高さや、インパクトの強さも捨てがたいと感じています。また、すでに「燃やす埋める」とラベル付けされた競技プログラミングの過去問が大量に存在することも無視できない事実です。与えられた問題を最小カット問題として定式化することに慣れていない人にとっては、それを「燃やす埋める」だと言及されることで、過去に「燃やす埋める」と呼ばれた問題群と同じ構造を持っていることを認識するキッカケになると考えています。

一方、テクニックを指す語「燃やす埋める」に対しては、むしろ悪影響を懸念しています。そもそも、頂点を「燃やす」「埋める」のように 2 択に分けること自体、まさにカットの定義そのものだからです。一般に、定義そのものを特別なテクニックと認識してしまうことには、悪影響がありそうです。たとえば、「頂点を 2 択に分けて解ける問題が、最小カットに帰着して解ける問題の一部である」という誤認を招く可能性が考えられます。そうではなく、「燃やす埋める」は、言い換えも不要なレベルでカットそのものなのです。頂点を 2 択に分けて解くという営みに対しては、純粋に「最小カットで解く」と言えば良いでしょう。

4-2： Historical Remark --- 競プロでの燃やす埋める

競技プログラミング界で、「プロジェクト $U_j$ を選択して、プロジェクト $V_j$ を選択しないとき、ペナルティ $C_j$」という条件を問う問題は、2000 年代後半にはすでに出題されていたようです。たとえば蟻本 [11] では、次の 3 問が取り上げられています。

POJ Monthly 2007 - Dual Core CPU（3-5 節の例題）
Google Code Jam 2009 World Final D - Wi-fi Towers（3-7 節の最終問題）
Google Code Jam 2008 World Final E - The Year of Code Jam（4-8 節の最終問題）

1 問目と 2 問目は、最小カットの考え方を素直に適用することで解ける問題です。3 問目は、それに加えてビット反転テクニック（8 章で解説します）を用いることで解けます。蟻本のボス問であり、2008 年の Gooble Code Jam 世界大会決勝で最も正答者数の少なかった問題と紹介されています。しかしながら、最小カットの考え方が広く普及した現代では、典型問題と捉えられるようになって来ており、類題も数多く作られています（9 章で多数紹介します）。

その後も 2010 年代前半には、TopCoder SRM などで繰り返し出題されました。当時の世界最先端の問題の雰囲気を知りたい方は、以下の資料を読んでみてください。

nico_shindannin: 最小カットを使って「燃やす埋める問題」を解く

AtCoder や日本国内の有志コンテストでは、2010 年代後半から、最小カットを問う問題が爆発的に流行するようになりました。そのキッカケとなったのは次の問題です。

AtCoder ARC 085 E - MUL（2017 年 11 月 11 日, Difficulty 2571）

これ以降、2018 年から 2020 年にかけて、大きく分けて 2 つの作問の流れが生まれました。1 つはより複雑な変数間の相互作用を扱うものを問う流れ（7 章）で、もう 1 つは $K$ 択を問う流れ（10 章）です。たとえば、次のような問題が作られました。

複雑な相互作用
- RUPC 2018 H - 板（2018 年 9 月 16 日）
- AtCoder AGC 038 F - Two Permutations（2019 年 9 月 21 日, Difficulty 3283）
$K$ 択
- KUPC 2019 H - 123パズル（2019 年 10 月 13 日）
- AtCoder ARC 107 F - Sum of Abs（2020 年 10 月 31 日, Difficulty 3130）

2021 年頃になると、これらの流れを統合した究極の一般形として、

Monge 関数の和は最小カットで解ける（11 章）

ことが理解されるようになって来ました（noshi [2]）。また、このことを問う問題も出題されています。

AtCoder ARC 129 E - Yet Another Minimization（2021 年 11 月 21 日, Difficulty 3337）
AtCoder ABC 347 G - Grid Coloring 2（2024 年 3 月 30 日, Difficulty 2876）

これらの問題は、最小カットとして表現できる範囲を一般化してきた歴史の集大成といえます。これ以降は、「一見 Monge 性を満たさないものに対して、Monge 性を満たすようにする上手い変数変換を問う」という方向の出題へとシフトしていきました。

AtCoder ARC 142 E - Pairing Wizards（2022 年 6 月 19 日, Difficulty 3232）
AtCoder ARC 176 E - Max Vector（2024 年 4 月 21 日, Difficulty 3101）

2026 年現在、この手の最小カットの問題で目新しいものを作ることは難しくなった......という空気感が漂っています。それでも、Monge 関数の和の最小化の出題の場が ARC から ABC に降りて来たのはごく最近のことです。むしろこれから、幅広く知られるようになり、各種の有志コンなどで流行していくのではないかと考えています。

5: プロジェクト選択問題の拡張 --- コストが負の場合など

それでは、プロジェクト選択問題を拡張していきましょう！　それによって、より多くの問題が解きやすくなります。

プロジェクト選択問題（再掲）

$N$ 個のプロジェクト $1, 2, \dots, N$ があり、どのプロジェクトを実行するかを選択したいとする。

プロジェクト $i$ を選択すると、$A_i$ ($\geq$ 0) だけコストがかかる
プロジェクト $i$ を選択しないと、$B_i$ ($\geq$ 0) だけコストがかかる

また、$M$ 個の条件がある。条件 $j$ は、次のものである。

プロジェクト $U_j$ を選択して、プロジェクト $V_j$ を選択しないとき、ペナルティとして $C_j$ ($\geq$ 0) だけコストがかかる

実行するプロジェクトを最適に選択するときの、コストの総和の最小値を求めよ。

5-1: Ai < 0 や Bi < 0 もあり得る場合

プロジェクト $i$ を選択するときのコスト $A_i$ や、選択しないときのコスト $B_i$ が負になることもある場合の対処法を考えましょう。コストが負であるということは「利得を与える」ということです。

実は簡単に対処できます。そもそもプロジェクト $i$ を選択するかしないかの 2 択を考えるとき、$A_i$ と $B_i$ の差が重要なのです。具体的な数値例を用いて、次のように考えることができます。

$A_i = -3$, $B_i = 9$ のときは、
- $A_i = 0$, $B_i = 12$ であるとして最小カット問題を解き、最後に $-3$ を足す
$A_i = -3$, $B_i = -9$ のときは、
- $A_i = 6$, $B_i = 0$ であるとして最小カット問題を解き、最後に $-9$ を足す

一般に、次のように考えればよいのです。

$A_i \ge B_i$ のとき：次のように考えて、最後に $B_i$ を足す
- プロジェクト $i$ を選択すると、$A_i - B_i$ のコストがかかる
- プロジェクト $i$ を選択しないと、コストがかからない
$A_i < B_i$ のとき：次のように考えて、最後に $A_i$ を足す
- プロジェクト $i$ を選択すると、コストがかからない
- プロジェクト $i$ を選択しないと、$B_i - A_i$ のコストがかかる

グラフで考えると、下図のように辺を張ればよいです。

Cj < 0 の場合は通常解けない

$A_i < 0$ や $B_i < 0$ の場合は扱えることが分かりました。それでは、$C_j < 0$ の場合を扱えるかを考えてみましょう。これはつまり、条件「$U_j$ を選択して、$V_j$ を選択しないときには、$-C_j$ の利得を与える」ということです。

結論からいうと、先ほどとは異なり、これは通常、最小カットでは解けません。

一般に、最大カット問題は NP 困難であることが知られています⁹。辺の重みが負であることは、符号を反転したグラフの最大カットを考えることを意味していて、一筋縄では行かないことが分かります。

5-2: プロジェクト u, v をともに選択する → 利得

しかしながら、「プロジェクト $u, v$ をともに選択するときに、負のコスト（利得）が発生する」という条件は、最小カットで扱うことができます。

条件を満たしたときに発生する利得を $P$ とします。これは、次のように考えることができます。

最初に、いかなる選択をとる場合にも、一律に利得 $P$ を与えておく
プロジェクト $u$ を選択しない場合に対して、$v$ を選択するかどうかにかかわらず、コスト $P$ を支払わせる
さらに、「プロジェクト $u$ を選択して、プロジェクト $v$ を選択しない」場合にコスト $P$ を支払わせる

（こうして、プロジェクト $u, v$ をともに選択する場合にのみ、利得 $P$ が残る）

具体的には、一律に利得 $P$ を先に与えた上で、次のように辺を張ったグラフの最小カットを求めればよいです¹⁰。

頂点 $s$ から頂点 $u$ へ、重み $P$ の辺を張る
頂点 $u$ から頂点 $v$ へ、重み $P$ の辺を張る

なお、「プロジェクト $u, v$ をともに選択するときにコストが発生する」という条件については、通常、最小カットで解くことはできません。

プロジェクト u, v をともに選択しない → 利得

同様に、「プロジェクト $u, v$ をともに選択しないときに、負のコスト（利得）が発生する」という条件も、最小カットで扱うことができます。一律に利得 $P$ を先に与えた上で、次のように辺を張ったグラフの最小カットを求めればよいです。

頂点 $v$ から頂点 $t$ へ、重み $P$ の辺を張る
頂点 $u$ から頂点 $v$ へ、重み $P$ の辺を張る

また、「プロジェクト $u, v$ をともに選択しないときにコストが発生する」という条件については、通常、最小カットで解くことはできません。

解ける問題と解けない問題の整理

プロジェクト $u, v$ の選択と、発生するものがコストか利得かに応じて、最小カットで解けるかどうかは下表のように整理できます。

$u$ の選択	$v$ の選択	コストか利得か	解けるかどうか
する	する	コスト	通常解けない
する	する	利得	解ける
する	しない	コスト	解ける
する	しない	利得	通常解けない
しない	する	コスト	解ける
しない	する	利得	通常解けない
しない	しない	コスト	通常解けない
しない	しない	利得	解ける

まとめると、

$u, v$ の選択が異なるときに、コストが発生する場合
$u, v$ の選択が等しいときに、利得が発生する場合

については、最小カットで解けると認識しておくとよいでしょう。

5-3: K 個のプロジェクトをすべて選択する → 利得

最後に、「$K$ 個のプロジェクトをすべて選択するときに、負のコスト（利得）が発生する」という条件を考えてみましょう。$K = 2$ の場合はすでに述べた通りです。$K \ge 3$ の場合は、上で述べた方法は通用しません。

簡単のために $K = 3$ として、条件「プロジェクト $a, b, c$ をすべて選択するときに利得 $P$ が発生する」を扱う方法を考えます。まず、「利得 $P$ を受け取る」という行為をするだけの仮想的なプロジェクト $x$ を導入します。そうすると、上の条件は次のように再構成できます。

プロジェクト $x$ を選択するならば、プロジェクト $a$ を選択しなければならない
プロジェクト $x$ を選択するならば、プロジェクト $b$ を選択しなければならない
プロジェクト $x$ を選択するならば、プロジェクト $c$ を選択しなければならない
プロジェクト $x$ の選択の有無にかかわらず一律に利得 $P$ を与えて、$x$ を選択しないことにコスト $P$ がかかるとする

これはグラフで表現できます。補助頂点 $x$ を用意して、次のように辺を張ったグラフの最小カットを求めればよいです。

頂点 $x$ から頂点 $a$ へ、重み $\infty$ の辺を張る
頂点 $x$ から頂点 $b$ へ、重み $\infty$ の辺を張る
頂点 $x$ から頂点 $c$ へ、重み $\infty$ の辺を張る
頂点 $s$ から頂点 $x$ へ、重み $P$ の辺を張る

K 個のプロジェクトを選択しない → 利得

同様に、条件「プロジェクト $a, b, c$ をすべて選択しないときに利得 $P$ が発生する」も扱えます。「利得 $P$ を受け取らない」という仮想的なプロジェクト $x$ を導入します（$x$ を選択しないとは、利得 $P$ を受け取るということです）。そうすると、上の条件は次のように再構成できます。

プロジェクト $a$ を選択するならば、プロジェクト $x$ を選択しなければならない
プロジェクト $b$ を選択するならば、プロジェクト $x$ を選択しなければならない
プロジェクト $c$ を選択するならば、プロジェクト $x$ を選択しなければならない
プロジェクト $x$ の選択の有無にかかわらず一律に利得 $P$ を与えて、$x$ を選択することにコスト $P$ がかかるとする

ここで、プロジェクト $x$ を選択することの意味を反転していることに注意しましょう。これは 8 章で詳しく解説するビット反転の一例にもなっています。ビット反転しないと、「プロジェクト $a, x$ をともに選択するときにコストが発生する」という条件になってしまい、最小カット問題に帰着できません。

また、グラフで表現すると、補助頂点 $x$ を用意して、次のように辺を張ったグラフの最小カットを求めればよいです。

頂点 $a$ から頂点 $x$ へ、重み $\infty$ の辺を張る
頂点 $b$ から頂点 $x$ へ、重み $\infty$ の辺を張る
頂点 $c$ から頂点 $x$ へ、重み $\infty$ の辺を張る
頂点 $x$ から頂点 $t$ へ、重み $P$ の辺を張る

6: 問題演習 Part. 1

ここまで、最小カット問題への帰着について、基本的な考え方を一通り概観しました。これらの考え方を試す意味も込めて、さまざまな問題を解いてみましょう！

6-1: 最小カット問題への帰着の思いつき方

競技プログラミング界では、しばしば「まずは全探索を考えることが大切だ」とよく言われます。この考え方は、最小カット問題への帰着においても重要です。最小カット問題に帰着できる問題は、大前提として

$2^N$ 通りの選択肢がある

（後編では、$K^N$ 通りの選択肢がある問題も扱います）

という構造をしています。つまり、$N$ 個の要素があって、それを「選択する」「選択しない」という 2 択があることが前提です。実は、競技プログラミングの問題を解いていると、$2^N$ 通りの選択肢がある問題は非常に多くみられます。ナップサック問題や最小点被覆問題などもそうですね。

パスや木に近い構造にできるならば、DP が疑われる

このとき、もし、$N$ 個の要素を一列に並べることができて、隣り合う要素間にしか制約条件がないのであれば、DP（動的計画法）で解けることが多いです。たとえば、「数列 $A_1, A_2, \dots, A_N$ から、隣り合わないようにいくつか選んで、総和を最大化せよ」という問題は DP で解けますね。少し難しい問題になると、

要素を上手くソートすることで、近い要素間にしか制約条件が発生しない構造にすることができるので、DP で解ける
最大値をとる要素の左右に分けて考えることで、木構造を見出すことができる（Cartesian 木）ので、木 DP で解ける
etc...

といったパターンもみられるようになります。

一方、$N$ 個の要素をどのような順番に並び替えても、要素間の制約条件が、パスや木に近い構造にならない場合には、DP で解くことは難しいです。無理矢理 DP で解くならば、いわゆる bit DP の出番となるケースが多いです。しかし、$N \le 50$ や $N \le 500$ といった制約の下では、bit DP では解けません。

凸性を見出すことができたら、フロー（や Greedy）が疑われる

要素間の制約条件がパスや木に近い構造にならないシチュエーションでは、最小カット問題への帰着が問われている可能性が高くなります¹¹。もし、制約条件が

$u, v$ の選択が異なるときに、コストが発生する
$u, v$ の選択が等しいときに、利得が発生する

という形にできるならば、最小カットで解けるのです。

なお、後編では、この考え方をさらに拡張します。実は、これらの条件は「ある種の凸性を満たしている」と言えます。劣モジュラ性・Monge 性・L 凸性や、マトロイド・M 凸性といった概念は、ある種の凸性を記述したものとなっています。凸であることがなぜ嬉しいかというと、

今ある解に対して改善を繰り返していったとき、これ以上改善できなくなったならば、最適性が保証される

からです。最小カット問題の解法である Ford-Fulkerson 法も、まさに、フローを流せなくなるまで流す（そして、流せなくなったら最適性が保証される）という解法ですね¹²。最小カット問題への帰着は、凸性を探すゲームだと言えます。

後編では、一見して凸性を満たしているとは思えないが、上手い変数変換をすると凸性を満たすようになる、というタイプの難問が多く登場します。

6-2: 簡単な問題（NoviSteps 3D 相当）

それでは、早速問題を解いていきましょう！　なお、以下に挙げる問題の解答例を示す際には、次のリンク先の構造体 ThreeVariableSubmodularOpt を用いることとし、main() 関数の中身のみを示すこととします。

問題 6：鉄則本 B68 - ALGO Express

ALGO 鉄道には $N$ 個の駅 $1, 2, \dots, N$ がある。いくつかの駅を特急駅に指定したい。

駅 $i$ を特急駅に指定すると、$P_i$ 円の利益が見込める（$P_i$ は負になることもある）。ただし、$M$ 個の制約条件がある。条件 $j$ は「駅 $A_j$ を特急駅に指定するならば、駅 $B_j$ も特急駅に指定しなければならない」というものである。

最大何円の利益を出すことができるか？

これはプロジェクト選択問題とよく似た形をしています。ただし、最大化問題であることに注意が必要です。今後すべての問題に言えることですが、最小カット問題への帰着を考える際には、まず最小化問題にすることが大切です。この問題を最小化問題にすると、次のようになります。

駅 $i$ を特急駅に指定すると、$-P_i$ 円のコストがかかる
駅 $A_j$ を特急駅に指定するならば、駅 $B_j$ も特急駅に指定しなければならない（これは変わりません）

このコスト条件下で最小化問題を解き、最後に $-1$ 倍したものが答えになります。

問題 6 の解答例

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N), A(M), B(M);
    for (int i = 0; i < N; i++) cin >> P[i];
    for (int j = 0; j < M; j++) cin >> A[j] >> B[j], A[j]--, B[j]--;

    ThreeVariableSubmodularOpt<int> opt(N);
    for (int i = 0; i < N; i++) opt.add_single_cost_10(i, -P[i], 0);
    for (int j = 0; j < M; j++) opt.add_psp_constraint_10(A[j], B[j]);
    cout << -opt.solve() << endl;
}

問題 7：競プロ典型 90 問 040 - Get More Money（★7)

$N$ 個の家 $1, 2, \dots, N$ がある。家 $i$ に入るためには $W$ のコストがかかるが、$A_i$ の利得が得られる。また、各家 $i$ に対して、次の $k_i$ 個の制約条件が付随している。

家 $i$ に入ることなくして、家 $c_{i, 1}$ $(> i)$ に入ることはできない
家 $i$ に入ることなくして、家 $c_{i, 2}$ $(> i)$ に入ることはできない
...
家 $i$ に入ることなくして、家 $c_{i, {k_i}}$ $(> i)$ に入ることはできない

これらの制約条件を満たしながら、いくつかの家に選んで入るとき、(総利得) - (総コスト) の考えられる最大値を求めよ。

今回も最大化問題ですので、まずは最小化問題に落としましょう。すると、次のようになります。

家 $i$ に入るときのコストは $W - A_i$、入らないときのコストは $0$
家 $c_{i, j}$ に入るならば、家 $i$ に入らなければならない ($j = 1, 2, \dots, k_i$)

このコスト条件下で最小カット問題を解き、最後に $-1$ 倍したものが答えになります。

問題 7 の解答例

int main() {
    int N, W;
    cin >> N >> W;
    vector<long long> A(N);
    vector<vector<long long>> c(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) {
        int k;
        cin >> k;
        c[i].resize(k);
        for (int j = 0; j < k; ++j) cin >> c[i][j], --c[i][j];
    }
    
    ThreeVariableSubmodularOpt<long long> opt(N);
    for (int i = 0; i < N; ++i) opt.add_single_cost_10(i, W - A[i], 0);
    for (int i = 0; i < N; ++i) for (auto v : c[i]) opt.add_psp_constraint_10(v, i);
    cout << -opt.solve() << endl;
}

問題 8： AtCoder ARC 085 E - MUL

$N$ 個の宝石 $1, 2, \dots, N$ がある。各宝石を割るか割らないかを決める。宝石 $i$ が割られずに残った場合、$A_i$ 円貰える（$A_i < 0$ の場合もある）。

ただし、宝石 $x$ を割るならば、番号が $x$ の倍数である宝石をすべて割らなければならない。

最大で何円お金を貰えるか？

Historical Remark でも紹介した問題です。やはり、最小化問題にすると、次のように整理できます。

宝石 $i$ を割るときのコストは $0$ 円、割らないときのコストは $-A_i$ 円
$y$ が $x$ の倍数であるような $x, y$ について、宝石 $x$ を割るならば、宝石 $y$ も割らなければならない

このコスト条件下で最小カット問題を解き、最後に $-1$ 倍したものが答えになります。

問題 8 の解答例

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    
    ThreeVariableSubmodularOpt<long long> opt(N);
    for (int i = 0; i < N; i++) opt.add_single_cost_10(i, 0, -A[i]);
    for (int x = 1; x <= N; x++) {
        for (int y = x * 2; y <= N; y += x) {
            opt.add_psp_constraint_10(x-1, y-1);
        }
    }
    cout << -opt.solve() << endl;
}

問題 9： AtCoder ABC 472 G - Cascading Grid

$H \times W$ のグリッドがあり、各マスは +, -, # のいずれかの文字が書かれている。以下の操作を $0$ 回以上行うことができる。

【操作】
# ではないマスを 1 つ選び、「選んだマスから # のマスを通ることなく、隣接するマスへ左・右・下のいずれかの方向に移動することだけで到達できるマス」をすべて # に変える

操作後のグリッドにおける、+ のマスの個数から - のマスの個数を引いた値としてあり得る最大値を求めよ。

これまでと一緒ですね。最小化問題として定式化すると、次のようになります。

マス $(i, j)$ を # に変えるときのコストは $0$
マス $(i, j)$ を # に変えないときのコストは、
- もともと + のとき: $-1$
- もともと - のとき: $1$
- もともと # のとき: $0$
マス $(i_1, j_1)$ からマス $(i_2, j_2)$ に到達できるとき、マス $(i_1, j_1)$ を # に変えるならば、マス $(i_2, j_2)$ も # に変えなければならない

ただし、最後の条件については、隣接するマス間についてのみ考えれば十分です。

問題 9 の解答例

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    ThreeVariableSubmodularOpt<int> opt(H * W);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        int not_choose_cost;
        if (S[i][j] == '+') not_choose_cost = -1;
        else if (S[i][j] == '-') not_choose_cost = 1;
        else not_choose_cost = 0;
        opt.add_single_cost_10(i * W + j, 0, not_choose_cost);
    }
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (S[i][j] == '#') continue;
        // 左
        if (j - 1 >= 0 && S[i][j - 1] != '#') {
            opt.add_psp_constraint_10(i * W + j, i * W + (j - 1));
        }
        // 右
        if (j + 1 < W && S[i][j + 1] != '#') {
            opt.add_psp_constraint_10(i * W + j, i * W + (j + 1));
        }
        // 下
        if (i + 1 < H && S[i + 1][j] != '#') {
            opt.add_psp_constraint_10(i * W + j, (i + 1) * W + j);
        }
    }
    cout << -opt.solve() << endl;
}

問題 10: ACPC 2019 H: Ghost (AOJ 3058)

文字 L, R からなる、長さ $N$ の文字列 $U$ が与えられる。今、文字列 $U$ の各文字を L または R に書き換えていくことによって、"恐怖度" を最小にしたい。

$M$ 個の恐怖要素があり、恐怖要素 $j$ は、次のものである。

$S$ の $S_j$ 文字目が R かつ $T_j$ 文字目が L であるとき、恐怖度は $B_j$ 加算される

ただし、文字 $i$ を書き換えると恐怖度は $A_i$ だけ増加する。最終的に得られる恐怖度の最小値を求めよ。

要素感の相互作用に関するペナルティが $\infty$ ではない問題も解いておきましょう。この問題は次のように定式化できます。

$i$ 文字目を R にするコストは、
- もともと R のとき; $0$
- もともと L のとき: $A_i$
$i$ 文字目を R にしないコストは、
- もともと R のとき; $A_i$
- もともと L のとき: $0$
$S_j$ 文字目が R である、かつ、$T_j$ 文字目が R ではないとき、$B_j$ のコストがかかる

このコスト条件下で最小カット問題を解きます。

問題 10 の解答例

int main() {
    int N, M;
    string U;
    cin >> N >> M >> U;
    vector<int> A(N), S(M), T(M), B(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int j = 0; j < M; j++) {
        cin >> S[j] >> T[j] >> B[j], S[j]--, T[j]--;
        if (S[j] > T[j]) swap(S[j], T[j]);
    }

    ThreeVariableSubmodularOpt<int> opt(N);
    for (int i = 0; i < N; i++) {
        opt.add_single_cost_10(i, (U[i] == 'R' ? 0 : A[i]), (U[i] == 'R' ? A[i] : 0));
    }
    for (int j = 0; j < M; j++) opt.add_psp_penalty_10(S[j], T[j], B[j]);
    cout << opt.solve() << endl;
}

6-3: 少し難しい問題（NoviSteps 4D 相当）

ここから少し難易度を高めた問題を解いていきます。

問題 11: RUPC 2018 H - 板 (AOJ 2903)

たとえば下図に示すような $H \times W$ グリッドが与えられます。各マスは . か # かいずれかである。

# の部分のみを、幅が $1$ の長方形型のタイルで敷き詰めたい。ただし、

タイルは縦向きか横向きの 2 方向でのみ設置が可能である
一つのマスに二枚以上のタイルが重なるように設置してはいけない

上記の制約を守って、最小何枚のタイルでこれが可能か？

##########
....#.....
....#.....
..........

（この場合は 2 枚）

とても美しい問題です！
各マスについて、「横向きのタイルで覆う」のか「縦向きのタイルで覆う」のかの 2 択を考えることとしましょう。そして、横方向に隣接する 2 マスについては、ともに横向きのタイルで覆えると嬉しいです。一方、縦方向に隣接する 2 マスについては、ともに縦向きのタイルで覆えると嬉しいです。このことに留意して、次のように定式化できます。

文字が # である各マスについて、横向きのタイルで覆うコストと、縦向きのタイルで覆うコストを、ともに 1 とする
横方向に隣接する 2 マスの # について、ともに横向きのタイルで覆うと、利得 $1$ を得る
縦方向に隣接する 2 マスの # について、ともに縦向きのタイルで覆うと、利得 $1$ を得る

一般に、プロジェクト選択において、選択が等しいときに利得が発生するケースは、最小カット問題に帰着できるのでした。次のコードのように解けます。なお、このコードでは、各マスに対して、横向きのタイルで覆う方を True、縦向きのタイルで覆う方を False としています。

問題 11 の解答例

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    ThreeVariableSubmodularOpt<int> opt(H * W);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (S[i][j] == '#') opt.add_single_cost_10(i * W + j, 1, 1);
    }
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (S[i][j] != '#') continue;
        
        // 横方向に隣接
        if (j + 1 < W && S[i][j + 1] == '#') {
            opt.add_both_true_profit(i * W + j, i * W + (j + 1), 1);
        }

        // 縦方向に隣接
        if (i + 1 < H && S[i + 1][j] == '#') {
            opt.add_both_false_profit(i * W + j, (i + 1) * W + j, 1);
        }
    }
    cout << opt.solve() << endl;
}

問題 12: AtCoder ABC 225 G - X

$H \times W$ グリッドの各マス $(i, j)$ には、値 $A_{i, j}$ が書かれている。

今、いくつかのマスを選んで、バツ印を書く。1 つのバツ印は、書かれるマスの左上の角と右下の角を結ぶ線分、および右上の角と左下の角を結ぶ線分の 2 本からなる。バツ印全体のスコアを、

$$\text{(バツ印を付けられたマスに書かれた整数の総和)} − C \times \text{(バツ印を書くために必要な線分の本数の最小値)}$$

と定義する。ここで、斜めに隣接するマスのバツ印を続けて書くことができることに注意する。たとえば、マス (1, 1) とマス (2, 2) にバツ印をつけるとき、

マス (1, 1) の左上の角とマス (2, 2) の右下の角を結ぶ 1 本の線分
マス (1, 1) の右上の角とマス (1, 1) の左下の角を結ぶ 1 本の線分
マス (2, 2) の右上の角とマス (2, 2) の左下の角を結ぶ 1 本の線分

の 3 本の線分によって、バツ印を書くことができる。

スコアの最大値を求めよ。

問題 11 とほとんど同様に解くことができます。斜めに隣接するマスについては、ともにバツ印をつけると $C$ の利得が得られると考えるとよいでしょう。次のように整理できます。

マス $(i, j)$ のコストは
- バツ印を書くとき: $2C - A_{i, j}$ （$2$ 本の線分を書くため）
- バツ印を書かないとき: $0$
斜め方向に隣接する 2 マスについて、ともにバツ印を書くならば、利得 $C$ を得る

これは、次のコードのように解くことができます¹³。

問題 12 の解答例

int main() {
    long long H, W, C;
    cin >> H >> W >> C;
    vector<vector<long long>> A(H, vector<long long>(W));
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> A[i][j];

    ThreeVariableSubmodularOpt<long long> opt(H * W);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        opt.add_single_cost_10(i * W + j, C * 2 - A[i][j], 0);
    }
    for (int i = 0; i + 1 < H; i++) for (int j = 0; j < W; j++) {
        // 左下
        if (j - 1 >= 0) {
            opt.add_both_true_profit(i * W + j, (i + 1) * W + (j - 1), C);
        }
        // 右下
        if (j + 1 < W) {
            opt.add_both_true_profit(i * W + j, (i + 1) * W + (j + 1), C);
        }
    }
    cout << -opt.solve() << endl;
}

問題 13: yukicoder No.2713 Just Solitaire

$N$ 枚のカード $1, 2, \dots, N$ があり、カード $i$ を使うには $A_i$ 円を消費する。

ただし、$M$ 種類のボーナスがある。ボーナス $i$ は次のものである。

$j = 1, 2, \dots, K_i$ に対して、カード $C_{i, j}$ が使われているならば、ボーナス $B_j$ 円を得る

使うカードを最適に選ぶことで、

(ボーナスによって獲得できる金額) - (カードを使うために消費する金額)

の最大値を求めよ。

この問題は、5-3 節で解説した「K 個のプロジェクトをすべて選択する → 利得」を試せる問題ですね。問題文に書いてある通りに定式化して解けばよいでしょう。

問題 13 の解答例

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> A(N), B(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];
    vector<vector<int>> C(M);
    for (int i = 0; i < M; i++) {
        int K;
        cin >> K;
        C[i].resize(K);
        for (int j = 0; j < K; j++) cin >> C[i][j], C[i][j]--;
    }

    ThreeVariableSubmodularOpt<long long> opt(N);
    for (int i = 0; i < N; i++) opt.add_single_cost_10(i, A[i], 0);
    for (int i = 0; i < M; i++) opt.add_all_true_profit(C[i], B[i]);
    cout <<  -opt.solve() << endl;
}

問題 14: AtCoder ARC 031 D - 買い物上手

$M$ 種類のアイテム $1, 2, \dots, M$ があり、アイテム $i$ は $T_i$ 円で入手できる。

また、アイテムを購入することで得られる「経験値」が $N$ 通りの組み合わせがある。$j$ 番目の組み合わせは次の通りである。

$K_j$ 個のアイテム $A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j}$ をすべて入手すると、経験値 $S_j$ がもらえる

入手するアイテムを上手く選ぶことで、「得られた経験値 ÷ 使ったお金」を最大化せよ。

この問題のように「比」や「平均値」といった値を最大化する問題では、頻繁に使える定石があります。それは、

$$\frac{\text{得られた経験値}}{\text{使ったお金}} > r$$

を満たす解が存在する $r$ の上限値を二分探索法によって求める、という手法です。俗に「食塩水典型」などとも呼ばれます。分母を払うと、次の判定問題が解ければよいことになります。

【判定問題】
$$r \times \text{使ったお金} - \text{得られた経験値}$$

の最小値が $0$ 未満であるかどうかを判定せよ。

ここから先は、プロジェクト選択問題で考えましょう。

アイテム $i$ を入手するとコスト $r \times T_i$、入手しないとコスト $0$
アイテム $A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j}$ をすべて入手すると、利得 $S_j$

いつも通り最小カットで解けます。

問題 14 の解答例

int main() {
    using DD = long double;
    int N, M;
    cin >> N >> M;
    vector<int> S(N), T(M);
    vector<vector<int>> A(N);
    for (int i = 0; i < N; i++) cin >> S[i];
    for (int i = 0; i < M; i++) cin >> T[i];
    for (int i = 0; i < N; i++) {
        int K;
        cin >> K;
        A[i].resize(K);
        for (int j = 0; j < K; j++) cin >> A[i][j], A[i][j]--;
    }
    DD low = 0, high = 1LL<<20;
    for (int iter = 0; iter < 40; iter++) {
        DD r = (low + high) / 2;
        ThreeVariableSubmodularOpt<DD> opt(M);
        for (int i = 0; i < M; i++) opt.add_single_cost_10(i, r * T[i], 0);
        for (int i = 0; i < N; i++) opt.add_all_true_profit(A[i], S[i]);
        if (opt.solve() < 0) low = r;
        else high = r;
    }
    cout << fixed << setprecision(10) << low << endl;
}

6-4: 現実世界への応用例

最後に、最小カット問題を用いた、現実世界への楽しい応用例をいくつか紹介します！

応用例 (1): 画像分割

「物体」と「背景」からなる画像が与えられて、画素ごとに「物体」なのか「背景」なのかを識別したい、という問題を考えましょう。たとえば、下図の左側の画像（飛行機という物体と、背景からなる）に対して、物体の部分を赤色と判定した結果が右側の画像です。

（参考文献 [13] より引用）

ㅤ

画像というものは、しばしばピンぼけなどによって、境界があやふやになっているものです。なるべく境界が滑らかになるように「物体」「背景」に分割したいとします。一方、各画素について、「おそらく物体に属しているだろう」「おそらく背景に属しているだろう」といった情報がある程度得られているとしましょう。

この状況を整理すると、次のような問題へとモデル化できます。これは、何度も議論してきたプロジェクト選択問題ですね。

問題 15: 画像分割問題

$H \times W$ グリッドが与えられて、各マスが「物体」か「背景」かを特定したい。マス $(i, j)$ の「物体っぽさ」は $A_{i, j}$、「背景っぽさ」は $B_{i, j}$ で与えられるとする。すなわち、

マス $(i, j)$ を「物体」と判定するときのコストは $B_{i, j}$、「背景」と判定するときのコストは $A_{i, j}$

とする。また、次の制約条件が課せられる。

隣接する 2 マスについて、片方を「物体」、他方を「背景」と判定するとき、$C$ のコストがかかる

コストが最小となるような画像分割を求めよ。

なお、本節紹介した画像分割問題は、マルコフ確率場における最大事後確率推定という分野に属する問題の一例といえます。この分野では、最も尤もらしいものを求めるための目的関数として、イジングモデルなどの統計物理モデルでも登場するエネルギー関数を用います。エネルギー関数の最小化は一般には難しい問題ですが、劣モジュラ性を仮定すると、最小カットで解くことができます。この話題に関心のある方は、参考文献 [5] を読んでてみてください。

ㅤ

応用例 (2): 最密部分グラフ

グラフネットワークが与えられたとき、最密な部分を求めることは、コミュニティ検出、ソーシャルネットワーク分析、金融ネットワークの不正検知などの分野で重要な問題です。これも最小カット問題として解くことができます。

問題 16: 最密部分グラフ問題

頂点数 $N$、辺数 $M$ の連結な単純無向グラフが与えられる。このグラフの空でない部分グラフに対して、

$$\text{密度} = \frac{\text{部分グラフに含まれる辺の本数}}{\text{部分グラフに含まれる頂点の個数}}$$

を考えるとき、その最大値を求めよ。

たとえば、以下のグラフでは、頂点 1, 3, 4, 5 を選んだときの密度は $\frac{5}{4}$ であり、これが最大である。

まず、問題 14 と同様に「食塩水典型」を用いて、二分探索法へ帰着しましょう。

$$\frac{\text{部分グラフに含まれる辺の本数}}{\text{部分グラフに含まれる頂点の個数}} > r$$

となる部分グラフが存在するような $r$ の上限値を二分探索法によって求めます。この式を変形すると、次の判定問題を解けば良いことがわかります。

【判定問題】
$$r \times \text{部分グラフに含まれる頂点の個数} - \text{部分グラフに含まれる辺の本数}$$

の最小値が $0$ 未満であるかどうかを判定せよ。

ここから先は、プロジェクト選択問題で考えてみましょう。各頂点 $v$ について、部分グラフに含めるかどうかを考えると、次のように整理できます。

頂点 $v$ を選ぶとコスト $r$、選ばないとコスト $0$
隣接する 2 頂点 $u, v$ について、ともに選ぶと、$1$ の利得が得られる

誤差についての注意

なお、実際に最密な部分グラフを抽出する際には、誤差に十分に注意する必要があります。誤差問題を回避するためには、$r$ を分母の十分大きな有理数として解く方法も考えられます。考えられる密度の差は高々 $\frac{1}{N(N-1)}$ であることから、たとえば $D = N^2$ として、

$$r = \frac{r^{\prime}}{D}$$

とおき、整数 $r^{\prime}$ の値を二分探索法によって絞る解法が考えられます。

競プロの問題

最密部分グラフ問題をテーマにした競プロの問題もあります。

ぜひトライしてみてください！

ㅤ

次回予告

後編では、まず最初に、プロジェクト選択問題で登場した

$u, v$ の選択が異なるときに、コストが発生する
$u, v$ の選択が等しいときに、利得が発生する

という形の条件が、ある種の凸性（劣モジュラ性・Monge 性）を満たすことを言います。そして、最終的には

Monge 関数の和は最小カットで解ける

ことを解説し、豊富な問題例を紹介します。

参考文献

[1] theore_and_me: 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性その②

[2] noshi: 最小カット問題の k 値への一般化

[3] 大槻兼資（著）, 秋葉拓哉（監修）: 問題解決力を鍛える！アルゴリズムとデータ構造

[4] J. Kleinberg, E. Tardos: アルゴリズムデザイン

[5] 河原由伸, 永野清仁: 劣モジュラ最適化と機械学習

[6] nico_shindannin: 最小カットを使って「燃やす埋める問題」を解く

[7] H. Lerchs and I. F. Grossmann: Optimum Design of Open-Pit Mines, 1965.

[8] J. M. W. Rhys: A Selection Problem of Shared Fixed Costs and Network Flows, 1970.

[9] J. C. Picard: Maximal Closure of a Graph and Applications to Combinatorial Problems, 1976.

[10] D. Hochbaum: Selection, provisioning, shared fixed costs, maximum closure, and implications on algorithmic methods today, 2004.

[11] 秋葉拓也, 岩田陽一, 北川宜稔: プログラミングコンテストチャレンジブック

[12] drken: 2 変数劣モジュラ関数のグラフ表現〜「燃やす埋める」の早見表〜

[13] 岡本吉央: グラフとネットワーク第 9 回　最大流：モデル化 (3) カットの視点

この相互作用は、劣モジュラ性と呼ばれる「極めてよい性質」を満たしていることも解説します。 ↩
★ の数は、AtCoder の過去問の難易度を 17 段階で評価するサイト AtCoder NoviSteps 上でのグレードに対応しています（グレード基準表）。★ は 3D、★★ は 3D+、★★★ は 4D、★★★★ は 4D+、★★★★★ は 5D に相当する話題です。 ↩
多くの文献では、カットの容量と呼ぶことが多いと思います。しかしながら、本記事では、最大流問題については解説せず、容量という語の出所がわかりにくいため、重みと呼ぶこととします。 ↩
ただし、文献による揺れもみられます。組合せ最適化の世界的大著である Schriver 氏の Combinatorial Optimization では、本記事におけるカットセットのことを、カットと呼んでいます。 ↩
最大流問題については本記事では詳しく触れませんが、最小カット問題は最大流問題の双対問題です。最大流問題は辺変数を最適化する問題ですので、その双対である最小カット問題は、頂点変数を最適化する問題であると捉えるのが自然です。 ↩
https://x.com/catupper/status/2091911746902712691?s=20 ↩
このことの略証を与えます。辺の集合 $X$ に属する辺をすべて取り除くと $s$ から $t$ へ到達不能になるとしましょう。このとき、到達不能となったグラフ上で頂点 $s$ から到達できる頂点の集合を $S$ とし、到達不能な頂点の集合を $T$ とすると、カット $(S, T)$ についてのカットセットは $X$ の部分集合になります。このことから、「問題 3: 最小コストグラフ破壊問題」の解として、カットセットのみ考えれば十分であることがいえます。 ↩
現在、当該記事は無くなっています。 ↩
最小カット問題を「辺を取り除くことで $s$ から $t$ へ到達不能にするための最小コスト」と捉えるノリで、最大カット問題を捉えると大変なことになります。「すべての辺を削除する」という一見自明な最適解があるように思えてしまいます。もちろん、これは誤りです。最大カット問題は、カットセットに含まれる辺の重みの総和が最大となるカットを求める問題です。 ↩
別解として、2 辺 $(s, v)$, $(v, u)$ を張る方法もあります。 ↩
他にも、自明な上界が存在することを示した上で、それを実際に達成できるケースを構築する、といった解法も考えられます。 ↩
フローをこれ以上流せなくなったら最適性が保証されるというのは、離散凸解析の言葉でいうと、M♮凸関数の最小化問題（M♮凸集合上の線形目的関数 $x_s$ の最小化問題）の最適性条件を示す例ともいえます。また、フローをこれ以上流せなくなったら最適性の証拠を与えるカットが見つかるということは、離散凸解析における Fenchel 双対性の中で理解することができます。 ↩
この問題は計算量解析の部分に若干の不備があったようです。しかしながら、一般にフローアルゴリズムは、実際上は最悪計算量よりも高速に動作することが多いものです。今回も素直にフローを流すことで AC を得ることができます。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

ネットワークフロー理論における「最小カット問題」の考え方・応用例を総整理！

目次

前編

後編（予告）

1： 最小カット問題

1-1： 最小カット問題とは

問題 1： 最小カット問題（重み無し）

問題 2： 最小カット問題（重み付き）

1-2： カットについてのよくある誤解 --- 「削除する辺の集合」ではない！

問題 3： 最小コストグラフ破壊問題

1-３： 最小カット問題の考え方の比較 --- 頂点集合の分割か、辺の削除か

1-4： 最小カットを求める方法

2： 最小カットは何を表すのか (1)：耐故障性

3： 最小カットは何を表すのか (2)：プロジェクト選択

3-1： カットを「プロジェクト選択」と解釈する

条件 A: プロジェクト 1 を選択すると 50 のコスト

条件 B: プロジェクト 2 を選択しないと 7 のコスト

条件 C: プロジェクト 3 を選択すると 4 のコスト、選択しないと 40 のコスト

条件 D: 「プロジェクト 1 を選択して、プロジェクト 2 を選択しない」ことにすると、100 のコスト

条件 E: 「プロジェクト 3 を選択して、プロジェクト 1 を選択しない」ことにすると、1000 のコスト

3-2： プロジェクト選択問題

問題 4： プロジェクト選択問題（Project Selection Problem）

3-3： プロジェクト選択問題を「辺の削除」で捉えると......

3-4: Historical Remark --- 露天掘り問題とプロジェクト選択問題

4： 燃やす埋める問題

4-1： 燃やす埋める問題とは

問題 5： 燃やす埋める問題（元ネタ）

燃やす埋めるというネーミングの是非について

4-2： Historical Remark --- 競プロでの燃やす埋める

5: プロジェクト選択問題の拡張 --- コストが負の場合など

プロジェクト選択問題（再掲）

5-1: Ai < 0 や Bi < 0 もあり得る場合

Cj < 0 の場合は通常解けない

5-2: プロジェクト u, v をともに選択する → 利得

プロジェクト u, v をともに選択しない → 利得

解ける問題と解けない問題の整理

5-3: K 個のプロジェクトをすべて選択する → 利得

K 個のプロジェクトを選択しない → 利得

6: 問題演習 Part. 1

6-1: 最小カット問題への帰着の思いつき方

パスや木に近い構造にできるならば、DP が疑われる

凸性を見出すことができたら、フロー（や Greedy）が疑われる

6-2: 簡単な問題（NoviSteps 3D 相当）

問題 6： 鉄則本 B68 - ALGO Express

問題 7： 競プロ典型 90 問 040 - Get More Money（★7)

問題 8： AtCoder ARC 085 E - MUL

問題 9： AtCoder ABC 472 G - Cascading Grid

問題 10: ACPC 2019 H: Ghost (AOJ 3058)

6-3: 少し難しい問題（NoviSteps 4D 相当）

問題 11: RUPC 2018 H - 板 (AOJ 2903)

問題 12: AtCoder ABC 225 G - X

問題 13: yukicoder No.2713 Just Solitaire

問題 14: AtCoder ARC 031 D - 買い物上手

6-4: 現実世界への応用例

応用例 (1): 画像分割

問題 15: 画像分割問題

応用例 (2): 最密部分グラフ

問題 16: 最密部分グラフ問題

誤差についての注意

競プロの問題

次回予告

参考文献

1：最小カット問題

1-1：最小カット問題とは

問題 1：最小カット問題（重み無し）

問題 2：最小カット問題（重み付き）

1-2：カットについてのよくある誤解 --- 「削除する辺の集合」ではない！

問題 3：最小コストグラフ破壊問題

1-３：最小カット問題の考え方の比較 --- 頂点集合の分割か、辺の削除か

1-4：最小カットを求める方法

2：最小カットは何を表すのか (1)：耐故障性

3：最小カットは何を表すのか (2)：プロジェクト選択

3-1：カットを「プロジェクト選択」と解釈する

3-2：プロジェクト選択問題

問題 4：プロジェクト選択問題（Project Selection Problem）

3-3：プロジェクト選択問題を「辺の削除」で捉えると......

4：燃やす埋める問題

4-1：燃やす埋める問題とは

問題 5：燃やす埋める問題（元ネタ）

問題 6：鉄則本 B68 - ALGO Express

問題 7：競プロ典型 90 問 040 - Get More Money（★7)