グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題！

問題へのリンク

問題概要

$N \times M$ のグリッドが与えられます。

各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害物マスは文字 '#' で表され、空マスは文字 '.' で表されます。

これらのマスに、 $1 \times 2$ の大きさのタイルを置きていきます。タイルは、縦または横に連続する 2 つの「空」マスの上に置くことができます。

最大でいくつのタイルを置くことができるか求めてください。また、実際にその最大値を達成する方法を 1 つ示してください。

制約

$1 \le N, M \le 100$

解法

人生で一度は解くべき典型問題ですね！　入力例 1 は、次のように 3 個のドミノを置くことができます。

この問題は、次の手順で解くことができます。

グリッドを市松模様に塗る
市松模様に塗ると、ドミノは「黒色マス」と「白色マス」のマッチングを表すので、二部マッチング問題に帰着できる
二部マッチング問題は、最大流問題へと帰着できる

Step 1：市松模様

まず、グリッド全体を市松模様に塗ってみましょう。ただし、障害物マス (文字 '#' のマス) には「❌」と描いています。

このとき、ドミノをどのように置いたとしても、ドミノは「黒色マス」と「白色マス」を 1 個ずつ占めることに注意しましょう。

Step 2：二部マッチング問題へ

一般に、最大二部マッチング問題とは、下図のように 2 つのカテゴリ (下図では「男」と「女」) のいくつかの要素間に辺があるとしたときに、最大で何ペアとれるかを求める問題です。

より正確に言えば、二部グラフが与えられたときに、互いに端点を共有しない辺をできるだけ多くとる問題です。

ここで、先ほどの市松模様を思い出しましょう。下図のように、各マスを頂点に対応させて、隣接するマス同士に辺を結んだようなグラフを考えます。ただし、各マスには順に番号を振っています。また、障害物マスに対応する頂点には辺を接続させないようにします。

このとき、このグラフは、「黒色マス」に対応する頂点と「白色マス」に対応する頂点の間に辺があるような二部グラフとなります。

ドミノは、黒色マスと白色マスを結ぶ辺に対応します。したがって、この問題は、与えられたグリッドに対応する二部グラフ上で、最大二部マッチングを求める問題に言い換えられることが分かりました。

たとえば、下図の左側のようなドミノタイリング (「マス 1, 2」「マス 3, 6」「マス 4, 7」の 3 ドミノ) は、下図の右側のようなマッチングに対応します。

Step 3：最大流問題へ

最大二部マッチング問題は、最大流問題へと帰着できることがよく知られています。この辺りの話題については、次の記事をぜひ読んでみてください。

qiita.com

最大流問題とは

さて、最大流問題とは、たとえば下図のような物流ネットワークにおいて、どれだけの流量を流せるかを問う問題です。供給地である地点 S から需要地である地点 T へと「もの」をできるだけたくさん運ぶ方法を考えます。

ただし、各輸送経路には運べる量の上限が設けられています。たとえば、地点 A から地点 B へは 37 トンの荷物を運ぶことができますが、地点 A から地点 C へは 4 トンの荷物しか運べません。また、地点 S と地点 T 以外の場所では物流を滞らせてもいけません。

つまり、例えば地点 B に地点 S と地点 A から合計して 6 トンの荷物が届いているならば、地点 B からは地点 C と地点 D へと合計して 6 トンの荷物を送らなければいけません。

さてこの輸送ネットワークでは最大で何トンの荷物を地点 S から地点 T へと送り出すことができるでしょうか？　答えは下図のように 9 トンとなります。なお、下図において、物流が上限一杯の経路は点線で示しています。

各輸送経路につき何トンの荷物を送るべきかを赤字で示しています。地点 S からは地点 A と地点 B にそれぞれ 5 トン、4 トンと合計 9 トン送り出しているのがわかります。地点 T には地点 C と地点 D からそれぞれ 7 トン、2 トンと合計 9 トンが届いているのがわかります。

また、物流が滞っていないかどうかを確かめるために地点 B を見てみましょう。地点 A と地点 S から合計 5 トンの荷物が届いていて、地点 C と地点 D へと合計 5 トンの荷物を送りだしていることがわかります。

二部マッチング問題を、最大流問題に帰着する

最後に、最大二部マッチング問題を、最大流問題へと帰着させる方法を考えます。

下図のように、二部グラフに対して、超頂点 S, T を追加して新たなネットワークを作ります。また、元の二部マッチングでは辺に向きはありませんでしたが、S と T を加えたネットワークには辺に向きがあります。また各辺の上限容量は 1 としておきます。

こうして作ったネットワークで最大流を流します。最後に、再び S と T を取っ払うと、最大二部マッチングが求まります。

コード

最大流問題を解くアルゴリズムについては、解説を他資料や他記事に譲ります。たとえば、けんちょん本 16 章で解説しています。

ここでは、ACL の提供している最大流アルゴリズムを活用します。ACL の提供するネットワークフロークラス mf_graph<Cap> (Cap は容量や流量を表す型) には、次のメソッドが用意されています。

int add_edge(int from, int to, Cap cap)：頂点 from から頂点 to へ、容量 cap の辺を張る (返り値は辺番号)
Cap graph.flow(int s, int t)：頂点 s から頂点 t への最大流を流す
vector<mf_graph<Cap>::edge> graph.edges()：辺集合を返す

なお、各辺を表す型 mf_graph<Cap>::edge は、次のようになっています。

struct mf_graph<Cap>::edge {
    int from, to;
    Cap cap, flow;
};

これらの仕様を元にして、グラフネットワークを構築して、最大流を流し、フローの流れた辺を特定して、ドミノタイリングを復元しましょう。

次のように実装できます。

ACL を用いた解答例

#include <bits/stdc++.h>
#include <atcoder/maxflow>
using namespace std;
using namespace atcoder;

// 上下左右を表すベクトル
const vector<int> DX = {1, 0, -1, 0};
const vector<int> DY = {0, 1, 0, -1};

int main() {
    // 入力受け取り
    int N, M;
    cin >> N >> M;
    vector<string> grid(N);
    for (int i = 0; i < N; ++i) cin >> grid[i];
    
    // フローネットワークを作る
    // 各マスの番号を 0, 1, ..., NM-1 とし、超頂点の番号を S = NM, T = NM+1 とする
    mf_graph<int> G(N * M + 2);
    int S = N * M, T = N * M + 1;
    
    // マス (i, j) の頂点番号を返す関数
    auto index = [&](int i, int j) -> int { return i * M + j; };
    
    // 黒色マスと白色マスを結ぶ (黒色：i + j が偶数、白色：i + j が奇数)
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            // 黒色マスならば、上下左右の 4 マスと辺を結んでいく
            if ((i + j) % 2 == 0) {
                for (int dir = 0; dir < 4; ++dir) {
                    int i2 = i + DX[dir], j2 = j + DY[dir];
                    if (i2 < 0 || i2 >= N || j2 < 0 || j2 >= M) continue;
                    
                    // どちらも空マスならば、ドミノを置けるので、辺を結ぶ
                    if (grid[i][j] == '.' && grid[i2][j2] == '.') {
                        G.add_edge(index(i, j), index(i2, j2), 1);
                    }
                }
            }
            
            // 超頂点 S から黒色マスへの辺を結ぶ
            if ((i + j) % 2 == 0 && grid[i][j] == '.') {
                G.add_edge(S, index(i, j), 1);
            }
            
            // 白色マスから超頂点 T への辺を結ぶ
            if ((i + j) % 2 == 1 && grid[i][j] == '.') {
                G.add_edge(index(i, j), T, 1);
            }
        }
    }
    
    // 最大流を流す
    int max_flow = G.flow(S, T);

    // フロー値が 1 となった辺を特定して、ドミノタイリングを復元する
    const auto &edges = G.edges();
    for (const auto &e : edges) {
        // 辺 e が超頂点に接続するものや、フロー値が 0 であるものはスキップ
        if (e.from == S || e.to == T || e.flow == 0) continue;
        
        // 辺 e の両端点に対応するマス
        int ifrom = e.from / M, jfrom = e.from % M;
        int ito = e.to / M, jto = e.to % M;
        
        // ドミノを置く
        if (ifrom == ito) {
            // ドミノを横に配置する場合
            if (jfrom > jto) swap(jfrom, jto);
            grid[ifrom][jfrom] = '>';
            grid[ito][jto] = '<';
        } else {
            // ドミノを縦に配置する場合
            if (ifrom > ito) swap(ifrom, ito);
            grid[ifrom][jfrom] = 'v';
            grid[ito][jto] = '^';
        }
    }
    
    // 出力
    cout << max_flow << endl;
    for (int i = 0; i < N; ++i) cout << grid[i] << endl;
}

自前ライブラリでも AC

自分用ライブラリでも通します。

github.com

#include <bits/stdc++.h>
using namespace std;

// edge class (for network-flow)
template<class FLOWTYPE> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOWTYPE cap, icap, flow;
    
    // constructor
    FlowEdge(int r, int f, int t, FLOWTYPE c)
    : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {}
    void reset() { cap = icap, flow = 0; }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowEdge& E) {
        return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOWTYPE>>> 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.assign(n, FlowEdge<FLOWTYPE>());
        pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOWTYPE>> &operator [] (int i) {
        return list[i];
    }
    const vector<FlowEdge<FLOWTYPE>> &operator [] (int i) const {
        return list[i];
    }
    size_t size() const {
        return list.size();
    }
    FlowEdge<FLOWTYPE> &get_rev_edge(const FlowEdge<FLOWTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    FlowEdge<FLOWTYPE> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowEdge<FLOWTYPE> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowEdge<FLOWTYPE>> get_edges() const {
        vector<FlowEdge<FLOWTYPE>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowEdge<FLOWTYPE> &e : list[i]) e.reset();
        }
    }
    void change_edge(FlowEdge<FLOWTYPE> &e, FLOWTYPE new_cap, FLOWTYPE new_flow) {
        FlowEdge<FLOWTYPE> &re = get_rev_edge(e);
        e.cap = new_cap - new_flow, e.icap = new_cap, e.flow = new_flow;
        re.cap = new_flow;
    }
    
    // add_edge
    void add_edge(int from, int to, FLOWTYPE cap) {
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(FlowEdge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(FlowEdge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

template<class FLOWTYPE> FLOWTYPE Dinic
 (FlowGraph<FLOWTYPE> &G, int s, int t, FLOWTYPE limit_flow)
{
    FLOWTYPE 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<FLOWTYPE> &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, FLOWTYPE up_flow) {
        if (v == t) return up_flow;
        FLOWTYPE res_flow = 0;
        for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
            FlowEdge<FLOWTYPE> &e = G[v][i], &re = G.get_rev_edge(e);
            if (level[v] >= level[e.to] || e.cap == 0) continue;
            FLOWTYPE 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) {
            FLOWTYPE flow = dfs(dfs, s, limit_flow - current_flow);
            if (!flow) break;
            current_flow += flow;
        }
    }
    return current_flow;
};

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


// ACL practice D
void ACL_practice_D() {
    // 上下左右を表すベクトル
    const vector<int> DX = {1, 0, -1, 0};
    const vector<int> DY = {0, 1, 0, -1};
    
    // 入力受け取り
    int N, M;
    cin >> N >> M;
    vector<string> grid(N);
    for (int i = 0; i < N; ++i) cin >> grid[i];
    
    // フローネットワークを作る
    // 各マスの番号を 0, 1, ..., NM-1 とし、超頂点の番号を S = NM, T = NM+1 とする
    FlowGraph<int> G(N * M + 2);
    int S = N * M, T = N * M + 1;
    
    // マス (i, j) の頂点番号を返す関数
    auto index = [&](int i, int j) -> int { return i * M + j; };
    
    // 黒色マスと白色マスを結ぶ (黒色：i + j が偶数、白色：i + j が奇数)
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            // 黒色マスならば、上下左右の 4 マスと辺を結んでいく
            if ((i + j) % 2 == 0 && grid[i][j] == '.') {
                for (int dir = 0; dir < 4; ++dir) {
                    int i2 = i + DX[dir], j2 = j + DY[dir];
                    if (i2 < 0 || i2 >= N || j2 < 0 || j2 >= M) continue;
                    
                    // どちらも空マスならば、ドミノを置けるので、辺を結ぶ
                    if (grid[i2][j2] == '.') {
                        G.add_edge(index(i, j), index(i2, j2), 1);
                    }
                }
            }
            
            // 超頂点 S から黒色マスへの辺を結ぶ
            if ((i + j) % 2 == 0 && grid[i][j] == '.') {
                G.add_edge(S, index(i, j), 1);
            }
            
            // 白色マスから超頂点 T への辺を結ぶ
            if ((i + j) % 2 == 1 && grid[i][j] == '.') {
                G.add_edge(index(i, j), T, 1);
            }
        }
    }
    
    // 最大流を流す
    int max_flow = Dinic(G, S, T);

    // フロー値が 1 となった辺を特定して、ドミノタイリングを復元する
    const auto &edges = G.get_edges();
    for (const auto &e : edges) {
        // 辺 e が超頂点に接続するものや、フロー値が 0 であるものはスキップ
        if (e.from == S || e.to == T || e.flow == 0) continue;
        
        // 辺 e の両端点に対応するマス
        int ifrom = e.from / M, jfrom = e.from % M;
        int ito = e.to / M, jto = e.to % M;
        
        // ドミノを置く
        if (ifrom == ito) {
            // ドミノを横に配置する場合
            if (jfrom > jto) swap(jfrom, jto);
            grid[ifrom][jfrom] = '>';
            grid[ito][jto] = '<';
        } else if (jfrom == jto) {
            // ドミノを縦に配置する場合
            if (ifrom > ito) swap(ifrom, ito);
            grid[ifrom][jfrom] = 'v';
            grid[ito][jto] = '^';
        }
    }
    
    // 出力
    cout << max_flow << endl;
    for (int i = 0; i < N; ++i) cout << grid[i] << endl;
}

int main() {
    ACL_practice_D();
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder Library Practice Contest D - Maxflow