SoundHound 2018 予選 C - 広告 (400 点)

ちょっと話題になった超典型フロー

問題へのリンク

問題概要

のグリッドがあります。各マスは白黒に塗られています。今、白いマスにできるだけ多くのコマを置きたいです。

• 各マスに 1 個のみ
• コマを置けるのは白いマスのみ
• 隣り合う白マスの双方にコマを置くのは禁止

という制約下で最大何個のコマを置けるか？

制約

• 

考えたこと

知っていれば一瞬の超典型問題ではある。
まずそもそもこの問題は、「グラフの最大安定集合問題」そのものの形をしている。最大安定集合問題については以下記事にて。

qiita.com

一般のグラフでは最大安定集合問題は NP-hard で解けない。しかし今回のグラフはグリッドグラフ (の部分グラフ) である。グリッドグラフは市松模様に塗ることができることからわかるように二部グラフである。そして、二部グラフの部分グラフももちろん二部グラフである。

よって問題のグラフは二部グラフなので、問題は「二部グラフの最大安定集合問題」ということになった。これは実はフローでとけることが知られている (上記記事参照)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


struct HopcroftKarp {
    int sizeL, sizeR;
    vector<vector<int> > list; // left to right
    
    // result
    vector<bool> seen, matched;
    vector<int> level, matching;
    
    // base
    HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { }
    inline vector<int>& operator [] (int i) { return list[i]; }
    inline void addedge(int from, int to) { list[from].push_back(to); }
    inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) {
        s << endl;
        for (int i = 0; i < G.list.size(); ++i) {
            s << i << " : ";
            for (int j = 0; j < G.list[i].size(); ++j) {
                s << G.list[i][j];
                if (j + 1 != G.list[i].size()) s << ", ";
            }
            s << endl;
        }
        return s;
    }
    
    // methods
    void hobfs() {
        queue<int> que;
        for (int left = 0; left < sizeL; ++left) {
            level[left] = -1;
            if (!matched[left]) {
                que.push(left);
                level[left] = 0;
            }
        }
        level[sizeL] = sizeL;
        while (!que.empty()) {
            int left = que.front();
            que.pop();
            for (int i = 0; i < list[left].size(); ++i) {
                int right = list[left][i];
                int next = matching[right];
                if (level[next] == -1) {
                    level[next] = level[left] + 1;
                    que.push(next);
                }
            }
        }
    }
    bool hodfs(int left) {
        if (left == sizeL) return true;
        if (seen[left]) return false;
        seen[left] = true;
        for (int i = 0; i < list[left].size(); ++i) {
            int right = list[left][i];
            int next = matching[right];
            if (level[next] > level[left] && hodfs(next)) {
                matching[right] = left;
                return true;
            }
        }
        return false;
    }
    int solve() {
        seen.assign(sizeL, false);
        matched.assign(sizeL, false);
        level.assign(sizeL+1, -1);
        matching.assign(sizeR, sizeL);
        int res = 0;
        while (true) {
            hobfs();
            seen.assign(sizeL, false);
            bool finished = true;
            for (int left = 0; left < sizeL; ++left) {
                if (!matched[left] && hodfs(left)) {
                    matched[left] = true;
                    ++res;
                    finished = false;
                }
            }
            if (finished) break;
        }
        return res;
    }
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    int R, C; cin >> R >> C;
    vector<string> fi(R);
    for (int i = 0; i < R; ++i) cin >> fi[i];

    HopcroftKarp hk(R*C, R*C);
    int V = R*C;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            int left = i * C + j;
            if (fi[i][j] == '*') {
                --V;
                continue;
            }
            if ( (i + j) % 2 == 1 ) continue;
            for (int dir = 0; dir < 4; ++dir) {
                int ni = i + dx[dir], nj = j + dy[dir];
                if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue;
                if (fi[ni][nj] == '*') continue;
                int right = ni * C + nj;
                hk.addedge(left, right);
            }
        }
    }
    auto res = hk.solve();
    cout << V - res << endl;
}