結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 WA -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 2 ms
4,376 KB
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 RE -
testcase_17 AC 10 ms
4,376 KB
testcase_18 AC 12 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 RE -
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 3 ms
4,376 KB
testcase_31 AC 11 ms
4,376 KB
testcase_32 AC 3 ms
4,376 KB
testcase_33 AC 3 ms
4,380 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 RE -
testcase_37 RE -
testcase_38 AC 14 ms
4,376 KB
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 WA -
testcase_48 AC 20 ms
4,376 KB
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 WA -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 WA -
testcase_59 RE -
testcase_60 AC 16 ms
4,380 KB
testcase_61 AC 6 ms
4,380 KB
testcase_62 RE -
testcase_63 AC 2 ms
4,376 KB
testcase_64 AC 2 ms
4,380 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) {
            if(s[i][j] == '.') continue;
            else if(s[i][j] == 'w') {
                mcf_graph.add_edge(st, i * h + j, 1);
                if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * h + j, i * h + j + 1, 1);
                if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge(i * h + j, (i + 1) * h + j, 1);
            } 
            else {
                mcf_graph.add_edge(i * h + j, go, 1);
                if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * h + j + 1, i * h + j, 1);
                if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge((i + 1) * h + j, i * h + j, 1);
            }
        }
    }
    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