結果

問題 No.421 しろくろチョコレート
ユーザー MitI_7MitI_7
提出日時 2016-10-03 22:39:11
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,254 bytes
コンパイル時間 1,093 ms
コンパイル使用メモリ 107,872 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-05-01 11:23:02
合計ジャッジ時間 4,398 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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);
    cout << p << endl;
    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