結果

問題 No.421 しろくろチョコレート
ユーザー sekiya9311
提出日時 2016-10-14 21:57:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 4,467 bytes
コンパイル時間 1,475 ms
コンパイル使用メモリ 130,196 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:10:16
合計ジャッジ時間 3,639 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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;
            }
        }
        return 0;
    }
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0