結果

問題 No.421 しろくろチョコレート
ユーザー boutarouboutarou
提出日時 2022-02-15 11:32:25
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 2,985 bytes
コンパイル時間 2,149 ms
コンパイル使用メモリ 210,328 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-11 16:59:33
合計ジャッジ時間 4,388 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 4 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 3 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 5 ms
4,380 KB
testcase_17 AC 9 ms
4,376 KB
testcase_18 AC 12 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 5 ms
4,376 KB
testcase_21 AC 4 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 2 ms
4,376 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 3 ms
4,380 KB
testcase_31 AC 11 ms
4,376 KB
testcase_32 AC 2 ms
4,376 KB
testcase_33 AC 4 ms
4,376 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 3 ms
4,380 KB
testcase_37 AC 14 ms
4,376 KB
testcase_38 AC 13 ms
4,376 KB
testcase_39 AC 2 ms
4,376 KB
testcase_40 AC 6 ms
4,376 KB
testcase_41 AC 2 ms
4,380 KB
testcase_42 AC 2 ms
4,376 KB
testcase_43 AC 2 ms
4,380 KB
testcase_44 AC 10 ms
4,380 KB
testcase_45 AC 2 ms
4,376 KB
testcase_46 AC 2 ms
4,376 KB
testcase_47 AC 4 ms
4,376 KB
testcase_48 AC 8 ms
4,380 KB
testcase_49 AC 3 ms
4,380 KB
testcase_50 AC 2 ms
4,376 KB
testcase_51 AC 11 ms
4,376 KB
testcase_52 AC 3 ms
4,380 KB
testcase_53 AC 2 ms
4,380 KB
testcase_54 AC 2 ms
4,376 KB
testcase_55 AC 2 ms
4,380 KB
testcase_56 AC 1 ms
4,376 KB
testcase_57 AC 2 ms
4,376 KB
testcase_58 AC 4 ms
4,380 KB
testcase_59 AC 3 ms
4,376 KB
testcase_60 AC 16 ms
4,380 KB
testcase_61 AC 6 ms
4,380 KB
testcase_62 AC 1 ms
4,380 KB
testcase_63 AC 1 ms
4,380 KB
testcase_64 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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