結果

問題 No.421 しろくろチョコレート
ユーザー sekiya9311sekiya9311
提出日時 2016-10-14 21:54:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 3,841 bytes
コンパイル時間 1,425 ms
コンパイル使用メモリ 127,552 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:10:04
合計ジャッジ時間 3,466 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <random>

#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a)-1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a)-1; (i) >= (b); (i)--)
#define PI acos(-1.0)
#define DEBUG(C) cerr << C << endl;
#define VI vector <int>
#define VII vector <VI>
#define VL vector <LL>
#define VLL vector <VL>
#define VD vector <double>
#define VDD vector <VD>
#define PII pair <int, int>
#define PDD pair <double, double>
#define PLL pair <LL, LL>
#define VPII vector <PII>
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define REVERSE(a) reverse(ALL(a))
#define MP make_pair
#define EB emplace_back
#define FORE(a, b) for (auto &&a : b)
#define FIND(s, n) (s.find(n) != s.end())

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

class FordFulkerson {
    struct edge {
        int to, rev;    //行き先，逆辺(のid)
        long long cap;  //容量
        edge(int _to, int _rev, long long _cap) {
            this->to = _to;
            this->rev = _rev;
            this->cap = _cap;
        }
    };
private:
    vector<vector<edge>> G;
    vector<bool> used;
    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        used[v] = true;
        FORE(el, G[v]) {
            if (used[el.to] || el.cap <= 0) {
                continue;
            }
            long long d = dfs(el.to, t, min(f, el.cap));
            if (d > 0) {
                el.cap -= d;
                G[el.to][el.rev].cap += d;
                return d;
            }
        }
        return 0;
    }
public:
    FordFulkerson() {}
    FordFulkerson(int n) {
        G.resize(n);
        used.resize(n, false);
    }
    void add_edge(int from, int to, long long cap) {
        G[from].emplace_back(edge(to, G[to].size(), cap));
        G[to].emplace_back(edge(from, G[from].size() - 1, 0));
    }
    long long max_flow(int s, int t) {
        if (s == t) return -1;
        long long flow = 0;
        while (1) {
            fill(begin(used), end(used), false);
            long long f = dfs(s, t, LLINF);
            if (f == 0) return flow;
            flow += f;
        }
    }
};

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int N, M;
bool inside(int ii, int jj) {
    return 0 <= ii && ii < N && 0 <= jj && jj < M;
}

int main(void) {
    cin >> N >> M;
    FordFulkerson mf(N * M + 10);
    int s = N * M, t = s + 1;
    vector<string> S(N);
    REP(i, N) cin >> S[i];
    int white = 0, black = 0;
    REP(i, N)REP(j, M) {
        if (S[i][j] == 'w') {
            white++;
            mf.add_edge(s, i * M + j, 1);
        }
        if (S[i][j] == 'b') {
            black++;
            mf.add_edge(i * M + j, t, 1);
            continue;
        }
        REP(k, 4) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (!inside(ni, nj)) continue;
            if (S[ni][nj] == '.') continue;
            mf.add_edge(i * M + j, ni * M + nj, 1);
        }
    }

    LL flow = mf.max_flow(s, t);
    LL ans = flow * 100;
    white -= flow;
    black -= flow;
    ans += min(white, black) * 10;
    ans += max(white, black) - min(white, black);
    cout << ans << endl;
}
0