結果

問題 No.421 しろくろチョコレート
ユーザー boutarou
提出日時 2022-02-15 11:32:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,985 bytes
コンパイル時間 2,490 ms
コンパイル使用メモリ 204,872 KB
最終ジャッジ日時 2025-01-27 23:15:37
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 6 "/mnt/c/Users/araar/documents/kyopro/library/graph/FordFulkerson.cpp"

template <typename T>
class FordFulkerson {
public:
    struct edge {
        int to;
        T cap;
        int rev;
    };

    int n;
    std::vector<std::vector<edge>> g;
    std::vector<bool> used;
    FordFulkerson(int n = 0)
        : n(n), g(n), used(n) {
    }
    void add_edge(int from, int to, T cap) {
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        assert(0 <= cap);
        g[from].push_back((edge){to, cap, int(g[to].size())});
        g[to].push_back((edge){from, 0LL, int(g[from].size() - 1)});
    }
    T dfs(int v, int goal_v, T flow) {
        if(v == goal_v) return flow;
        used[v] = true;
        for(int i = 0; i < (int)g[v].size(); i++) {
            edge &e = g[v][i];
            if(!used[e.to] && e.cap > 0) {
                T next_flow = dfs(e.to, goal_v, std::min(flow, e.cap));
                if(next_flow > 0) {
                    e.cap -= next_flow;
                    g[e.to][e.rev].cap += next_flow;
                    return next_flow;
                }
            }
        }
        return 0;
    }
    T max_flow(int s, int t, T ma = std::numeric_limits<T>::max()) {
        assert(0 <= s && s < n);
        assert(0 <= t && t < n);
        T flow = 0;
        while(1) {
            used = std::vector<bool>(n, false);
            T f = dfs(s, t, ma);
            if(f == 0) return flow;
            flow += f;
        }
    }
};
#line 3 "main.cpp"
using namespace std;
#define rep(i, n) for(int i = 0; i < int(n); i++)
using ll = long long;
using P = pair<int, int>;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    FordFulkerson<int> mcf_graph(h * w + 2);
    int st = h * w, go = h * w + 1;
    rep(i, h) {
        rep(j, w) {
            // cout << i * w + j << " ";
            if(s[i][j] == '.')
                continue;
            else if(s[i][j] == 'w') {
                mcf_graph.add_edge(st, i * w + j, 1);
                if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * w + j, i * w + j + 1, 1);
                if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge(i * w + j, (i + 1) * w + j, 1);
            }
            else {
                mcf_graph.add_edge(i * w + j, go, 1);
                if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * w + j + 1, i * w + j, 1);
                if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge((i + 1) * w + j, i * w + j, 1);
            }
        }
        // cout << endl;
    }
    int flowcnt = mcf_graph.max_flow(st, go);

    int bcnt = 0, wcnt = 0;
    rep(i, h) rep(j, w) {
        if (s[i][j] == 'w') wcnt++;
        else if (s[i][j] == 'b')
            bcnt++;
    }
    cout << 100 * flowcnt + (min(bcnt, wcnt) - flowcnt) * 10 + max(bcnt, wcnt) - min(bcnt, wcnt) << endl;
    // cout << flowcnt << endl;
    return 0;
}
0