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

今回は、最小カット問題について書いていきます。最小カット問題は、情報系の大学では「アルゴリズムとデータ構造」の講義の終盤で少しだけ登場するマニアックな話題というイメージを持たれる方が多いかもしれません。しかしながら、とても美しい構造を持っており、現実世界への応用も多方面に広がっています。よく分からなかった......で済ませるのは大変もったいないです。

一般に、問題は効率よく解けるものと解きにくいものがありますが、最小カット問題は「解ける」問題に代表的な構造を有しています。最小カット問題について習熟することで、解ける問題を見抜く勘を鍛えたり、一般には解けない問題に対しても仮定を置くことで解けるようにするなどができるようになります。

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

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

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

目次

各章の（）の中の ★ の個数は難易度を表します1。長いので、「前編」と「後編」に分けて扱います。本記事は「前編」に相当します。

前編

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)$ 的權重2。使用這個定義，最小カット問題就是「求權重最小的割」。

問題 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$ 側」兩種選擇。

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

如上所示，請注意，割是針對頂點的定義，割集是針對邊的定義3。對於割，常會因字面印象而誤以為它就是「透過刪除可使 $s$ 無法到達 $t$ 的邊集合」——這是很常見的誤解。畢竟，割的定義本來就是針對頂點4。

這種誤解產生的背景，我想有一部分原因在於：「刪除後使 $s$ 無法到達 $t$ 的邊權重總和最小值」這類問題，常被當作最小割能解的第一個例題來介紹5。

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

給定帶權有向圖與 2 個頂點 $s, t$（權重非負）。

現在，想透過刪除一些邊，使得無法從頂點 $s$ 到達頂點 $t$。求被刪除邊的權重總和最小值。

這個問題的解，可以由最小割問題的最佳解構造出來。舉例來說，在上面「問題 2：最小カット問題（重み付き）」所示的圖中，刪除紅色粗線邊後，如下圖所示。可以看出已經無法從 $s$ 到達 $t$。一般而言，最小割問題的最佳解（最佳割）之割集，也會是問題 3 的最佳解6。

補充一下，下面的包含關係成立。對於割 $(S, T)$ 的割集（即從 $S$ 側流向 $T$ 側的邊集合），一般而言都滿足「刪除後可使 $s$ 到 $t$ 不可達」這個性質。反過來，刪除後雖然能讓 $s$ 到 $t$ 不可達，但這些邊集合未必是割集。

例如，下圖中紅色粗線表示的邊集合，雖然滿足「刪除後使 $s$ 無法到達 $t$」這個性質，但它不是割集。

即便如此，

（割集的權重最小值）=（使 $s$ 到 $t$ 不可達而需刪除的邊權重最小值）

仍然成立。一般而言，在解最佳化問題時，證明「即使將考察對象縮小，最佳解仍包含其中」是很有效的。對最小割問題也是如此，因此常將其定式化為求割集權重最小值的問題。

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

到目前為止，我們看到最小割有兩種看法。

• 想法 (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] 等。另一種更基礎的 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： カットを「プロジェクト選択」と解釈する

這裡假設圖的頂點代表專案（也就是要決定是否執行的項目）。接著考慮一種情況：圖的割與專案選擇是一對一對應。也就是說，

• $S$ 側的頂點所對應的專案，選擇
• $T$ 側的頂點所對應的專案，不選擇

例如，假設有專案 1, 2, 3，其對應圖如下。來想想看，這張圖要如何用「專案選擇」的語言來解釋。

結論先講，這張圖可以用專案選擇的語言解釋成以下內容。

【專案選擇的成本條件】

• 條件 A：選擇專案 1，會產生 50 的成本
• 條件 B：不選擇專案 2，會產生 7 的成本
• 條件 C：選擇專案 3 會產生 4 的成本，不選擇則會產生 40 的成本
• 條件 D：「選擇專案 1、且不選擇專案 2」時，會產生 100 的成本
• 條件 E：「選擇專案 3、且不選擇專案 1」時，會產生 1000 的成本

也就是說，「求上圖的最小割」與「在上述成本條件下選出總成本最小的專案集合」，完全是一樣的。下面會詳細說明。

另外，具體的最佳解是如上圖所示的割（之後在圖示割時，只畫出 $S$，不畫 $T$），即 $S =$ {$s, 2$}、$T =$ {$t, 1, 3$}，其割的權重為 40，對應的專案選擇是：

• 不選擇專案 1
• 選擇專案 2
• 不選擇專案 3

也就是最小成本 40。

條件 A: 選擇專案 1 會產生 50 的成本

接著逐一檢討專案選擇的成本條件。先看條件 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 的成本」。這個條件對應到圖中的兩條邊 $(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 則是關於兩個專案 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： プロジェクト選択問題

到這裡，我們已經看過，圖的「割」與專案的「選擇」可以一對一對應，並且圖中邊的權重可以解釋如下。

邊的權重｜專案選擇中的解釋
始點是 $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]）。在露天採礦問題中，會把礦床切成 3D 方塊，每個方塊 $i$ 擁有價值

$$ w_i= \text{礦石價值}-\text{採掘費用} $$

若是礦石，可能有 $w_i > 0$；若是廢石，可能有 $w_i < 0$。然而，不能突然只挖地下深處有價值的方塊。由於邊坡穩定性，挖某個方塊時，必須先挖它上方的方塊......這類條件就是專案選擇問題中處理的內容。

另一方面，專案選擇問題本身，與露天採礦問題無關，約在 1970 年前後也被廣泛研究（如 Rhys, 1970 [8]）。之後，Picard, 1976 [9] 將露天採礦問題與專案選擇問題統一抽象化，並整理成網路流理論的一部分。

這些歷史脈絡整理於 Hochbaum, 2004 [10]。有興趣的話請務必閱讀。

4： 燃やす埋める問題

接下來，來看「燃やす埋める」問題。

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

下面展示了大家所稱的「燃やす埋める」問題群的起源。這是 Komaki 在自己的文章中提出的問題7。其本質上就是專案選擇問題。

Komaki 本人並沒有把它命名為「燃やす埋める」，但由於該問題設定帶來的衝擊力，之後便逐漸被稱為「燃やす埋める」問題。此外，也因此形成了一種文化：把每個頂點分成「燃やす」與「埋める」兩種選擇的技巧，也被稱為「燃やす埋める」。

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

有 $N$ 份垃圾。對每份垃圾，需選擇要燒掉還是埋掉。

• 燒掉垃圾 $i$ 需要 $A_i$（$\geq 0$）元
• 埋掉垃圾 $i$ 需要 $B_i$（$\geq 0$）元

但有 $M$ 個限制條件。第 $j$ 個限制如下：

• 當燒掉垃圾 $U_j$ 且埋掉垃圾 $V_j$ 時，會作為懲罰產生 $C_j$（$\geq 0$）元的成本

求將所有垃圾都燒掉或埋掉時，總成本的最小值。

燃やす埋める這個命名是否恰當

這裡我想重新討論一下「燃やす埋める」這個名稱是否恰當。就我個人而言，對於指稱問題的「燃やす埋める」是偏正面的；但對於指稱技巧的「燃やす埋める」則是偏負面的。例如，我會認同「這題是燃やす埋める問題」這種說法，但不太認同「這題可以用燃やす埋める解」這種說法。

對於指稱問題的「燃やす埋める」，確實要注意，世界上還存在一個更廣為接受的名稱，也就是「專案選擇問題」。不過，「燃やす埋める」這個名稱在 Google 上很容易搜尋到，而且衝擊力很強，這點也很難忽視。另外，既然已經存在大量被標記為「燃やす埋める」的競賽程式設計舊題，這也是無法否認的事實。對還不習慣把題目定式化成最小割問題的人來說，若聽到「這是燃やす埋める」，反而可能因此意識到：原來它和過去被稱為「燃やす埋める」的題目群有相同的結構。

另一方面，對於指稱技巧的「燃やす埋める」，我反而比較擔心會有負面影響。因為說到底，把頂點分成「燃やす」與「埋める」兩選一，本來就是割的定義本身。一般而言，把定義本身當成某種特殊技巧來看待，似乎容易造成誤解。例如可能會讓人以為：「能夠把頂點分成兩選一來解的問題，只是最小割可解問題的一部分。」但其實不是這樣；「燃やす埋める」本質上就是割本身，甚至不需要另起新名詞。對於這種把頂點分成二選一來解題的做法，直接說「用最小割解」就好了。

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 年 Google Code Jam 世界總決賽中正解人數最少的題目。然而在最小割的想法普及的現代，它已被視為典型題，相關題目也被大量出題（第 9 章會介紹很多）。

之後在 2010 年代前半，TopCoder SRM 等也反覆出現相關題目。若想了解當時世界最前沿題目的氛圍，可以閱讀以下資料：

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

到了 AtCoder 與日本國內有志競賽中，從 2010 年代後半開始，最小割題目開始爆炸性流行。引爆這股潮流的題目如下：

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

之後在 2018 年到 2020 年之間，大致產生了 2 種作題方向。一種是處理更複雜的變數間互動（第 7 章），另一種是 $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$ 要不要選時，$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 困難的8。邊權為負，代表相當於在符號反轉後的圖上考慮最大割，顯然沒那麼簡單。

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

原文出處：https://qiita.com/drken/items/52aafd8c073b37749539