結果

問題 No.421 しろくろチョコレート
ユーザー sekiya9311sekiya9311
提出日時 2016-10-14 21:50:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,449 bytes
コンパイル時間 1,736 ms
コンパイル使用メモリ 130,868 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-05-01 23:07:06
合計ジャッジ時間 10,514 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 1 ms
6,940 KB
testcase_14 RE -
testcase_15 AC 2 ms
6,944 KB
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 AC 1 ms
6,944 KB
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
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 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'long long int Dinic::dfs(int, int, long long int)':
main.cpp:105:5: warning: control reaches end of non-void function [-Wreturn-type]
  105 |     }
      |     ^

ソースコード

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 Dinic {
private:
    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;
        }
    };
    vector<vector<edge>> G;
    vector<int> dist;   //sからの距離
    vector<int> iter;   //どこまで調べ終わったか
    //sからの最短経路探索(distに格納)
    void bfs(int s) {
        fill(begin(dist), end(dist), -1);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        while (!q.empty()) {
            int now = q.front(); q.pop();
            FORE(el, G[now]) {
                if (el.cap > 0 && dist[el.to] < 0) {
                    dist[el.to] = dist[now] + 1;
                    q.push(el.to);
                }
            }
        }
    }
    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int &id = iter[v]; id < G[v].size(); id++) {
            edge &el = G[v][id];
            if (el.cap <= 0 || dist[v] >= dist[el.to]) {
                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;
            }
        }
    }
public:
    Dinic() {}
    Dinic(int n) {
        G.resize(n);
        dist.resize(n, -1);
        iter.resize(n, 0);
    }
    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 0;
        long long flow = 0;
        while (1) {
            bfs(s);
            if (dist[t] < 0) return flow;
            fill(begin(iter), end(iter), 0);
            long long f = dfs(s, t, LLINF);
            if (f > 0) 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;
    Dinic 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