結果

問題 No.421 しろくろチョコレート
ユーザー MitI_7MitI_7
提出日時 2016-10-03 22:39:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 202 ms / 2,000 ms
コード長 4,236 bytes
コンパイル時間 1,324 ms
コンパイル使用メモリ 107,232 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:10:09
合計ジャッジ時間 4,030 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 30 ms
6,940 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 22 ms
6,940 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 4 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 9 ms
6,940 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 1 ms
6,944 KB
testcase_16 AC 27 ms
6,940 KB
testcase_17 AC 109 ms
6,940 KB
testcase_18 AC 154 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 39 ms
6,940 KB
testcase_21 AC 26 ms
6,940 KB
testcase_22 AC 9 ms
6,944 KB
testcase_23 AC 1 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 1 ms
6,944 KB
testcase_26 AC 1 ms
6,944 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 3 ms
6,940 KB
testcase_29 AC 9 ms
6,944 KB
testcase_30 AC 11 ms
6,940 KB
testcase_31 AC 17 ms
6,944 KB
testcase_32 AC 6 ms
6,940 KB
testcase_33 AC 23 ms
6,944 KB
testcase_34 AC 2 ms
6,940 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 16 ms
6,944 KB
testcase_37 AC 167 ms
6,944 KB
testcase_38 AC 169 ms
6,940 KB
testcase_39 AC 6 ms
6,944 KB
testcase_40 AC 27 ms
6,944 KB
testcase_41 AC 12 ms
6,944 KB
testcase_42 AC 4 ms
6,944 KB
testcase_43 AC 8 ms
6,940 KB
testcase_44 AC 51 ms
6,940 KB
testcase_45 AC 3 ms
6,944 KB
testcase_46 AC 4 ms
6,940 KB
testcase_47 AC 34 ms
6,944 KB
testcase_48 AC 21 ms
6,940 KB
testcase_49 AC 6 ms
6,940 KB
testcase_50 AC 3 ms
6,940 KB
testcase_51 AC 103 ms
6,940 KB
testcase_52 AC 16 ms
6,944 KB
testcase_53 AC 3 ms
6,940 KB
testcase_54 AC 5 ms
6,940 KB
testcase_55 AC 2 ms
6,940 KB
testcase_56 AC 2 ms
6,944 KB
testcase_57 AC 3 ms
6,940 KB
testcase_58 AC 27 ms
6,944 KB
testcase_59 AC 6 ms
6,940 KB
testcase_60 AC 202 ms
6,944 KB
testcase_61 AC 29 ms
6,940 KB
testcase_62 AC 1 ms
6,940 KB
testcase_63 AC 2 ms
6,940 KB
testcase_64 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <fstream>
#include <bitset>
#include <time.h>
#include <assert.h>

#define LL long long
#define FOR(i,a,b) for(int i= (a); i<((int)b); ++i)
#define RFOR(i,a) for(int i=(a); i >= 0; --i)
#define FOE(i,a) for(auto i : a)
#define SZ(x) ((int)(x).size())
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define AND &&
#define OR ||
#define NOT !
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define EPS 1e-14

template<typename T> inline void DUMP(T x) { std::cerr << x << std::endl; }
template<typename T> inline void DUMP_V(std::vector<T> v) { for (unsigned int i = 0; i < v.size(); ++i) { std::cerr << v[i] << ((i == v.size() - 1) ? "n" : " "); } }
template<typename T> inline void DUMP_V2(std::vector<std::vector<T>> v) { for (unsigned int i = 0; i < v.size(); ++i) { for (unsigned int j = 0; j < v[i].size(); ++j) { std::cerr << v[i][j] << " "; } std::cerr << std::endl; } }

using namespace std;

class FordFulkerson {
private:
    struct Edge { int to; int capacity; int rev; }; // 辺(行き先、容量、逆辺のidx(Graph[to][rev]でアクセス))
    map<int, vector<Edge>> Graph;                   // グラフ(ノード番号: {辺1, 辺2, ...})

    // fromからtoまでの増加パスをDFSで探す
    int dfs(int from, int sink, int flow, set<int> &used) {
        if (from == sink) return flow;

        used.insert(from);
        for (Edge &e : Graph[from]) {
            if (used.find(e.to) == used.end() && e.capacity > 0) {
                int d = dfs(e.to, sink, min(flow, e.capacity), used);

                // 流せる
                if (d > 0) {
                    e.capacity -= d;
                    Graph[e.to][e.rev].capacity += d;
                    return d;
                }
            }
        }

        // fromからtoへのパスがみつからない
        return 0;
    }

public:
    // グラフに辺を追加
    void addEdge(int from, int to, int capacity) {
        Graph[from].push_back({ to, capacity, (int)Graph[to].size() });
        Graph[to].push_back({ from, 0, (int)Graph[from].size() - 1 });
    }

    // sourceからsinkへの最大流を求める
    // O(F|E|) Fは最大の流量
    int maxFlow(int source, int sink) {
        int flow = 0;
        while (true) {
            set<int> used;
            int f = dfs(source, sink, INT_MAX, used);
            if (f == 0) { break; };
            flow += f;
        }
        return flow;
    }
};


// 4近傍（右, 下, 左, 上）
vector<int> dy = { 0, -1, 0, 1 };
vector<int> dx = { 1, 0, -1, 0 };

bool inside(int y, int x, int H, int W) {
    return 0 <= y && y < H && 0 <= x && x < W;
}

int main(int argc, char *argv[]) {
    FordFulkerson ff;
    
    int n, m;
    string s;
    vector<string> v;
    cin >> n >> m;
    FOR(i, 0, n) {
        cin >> s;
        v.push_back(s);
    }

    int source = n * m + 1;
    int sink = n * m + 2;
    int w = 0;
    int b = 0;
    FOR(y, 0, n) {
        FOR(x, 0, m) {
            int node = y * m + x;

            if (v[y][x] == 'w') {
                w++;

                ff.addEdge(source, node, 1);

                for (int i = 0; i < dy.size(); i++) {
                    int ny = y + dy[i];
                    int nx = x + dx[i];

                    if (inside(ny, nx, n, m)) {
                        if (v[ny][nx] == 'b') {
                            int black = ny * m + nx;
                            ff.addEdge(node, black, 1);
                        }
                    }
                }

                
            }
            else if (v[y][x] == 'b') {
                b++;
                ff.addEdge(node, sink, 1);
            }
            
        }
    }
    int ans = 0;
    int p = ff.maxFlow(source, sink);
    
    ans += p * 100;

    w -= p;
    b -= p;

    int t = min(w, b);
    ans += t * 10;
    
    ans += max(w, b) - t;
    
    cout << ans << endl;
    
    return 0;
}
0