結果

問題 No.421 しろくろチョコレート
ユーザー tokusakuraitokusakurai
提出日時 2020-08-19 16:16:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 2,855 bytes
コンパイル時間 2,516 ms
コンパイル使用メモリ 205,020 KB
最終ジャッジ日時 2025-01-13 03:50:36
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<typename T>
struct Max_Flow{
    struct edge{
        int to; T cap; int rev;
        edge(int to, T cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    vector<vector<edge>> es;
    vector<bool> used;
    const T INF_T;

    Max_Flow(int n) : INF_T(numeric_limits<T>::max()){
        es.resize(n), used.resize(n);
    }

    void add_edge(int from, int to, T cap, bool directed = true){
        es[from].eb(to, cap, sz(es[to]));
        es[to].eb(from, directed? 0 : cap, sz(es[from])-1);
    }

    T dfs(int now, int t, T flow){
        if(now == t) return flow;
        used[now] = true;
        for(auto &e: es[now]){
            if(!used[e.to] && e.cap > 0){
                T f = dfs(e.to, t, min(flow, e.cap));
                if(f > 0){
                    e.cap -= f;
                    es[e.to][e.rev].cap += f;
                    return f;
                }
            }
        }
        return 0;
    }

    T max_flow(int s, int t){
        T flow = 0;
        for(;;){
            fill(all(used), false);
            T f = dfs(s, t, INF_T);
            if(f == 0) return flow;
            flow += f;
        }
    }
};

int main(){
    int H, W;
    cin >> H >> W;
    int N = H*W;
    string S[H];
    rep(i, H) cin >> S[i];
    Max_Flow<int> G(2*N+2);
    int s = 2*N, t = 2*N+1;
    int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    int b = 0, w = 0;
    rep(i, H){
        rep(j, W){
            if(S[i][j] == '.') continue;
            if(S[i][j] == 'b'){
                b++;
                G.add_edge(s, W*i+j, 1);
                rep(k, 4){
                    int ni = i+dx[k], nj = j+dy[k];
                    if(ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
                    G.add_edge(W*i+j, N+W*ni+nj, 1);
                }
            }
            else{
                w++;
                G.add_edge(N+W*i+j, t, 1);
            }
        }
    }
    int f = G.max_flow(s, t);
    if(b < w) swap(b, w);
    int ans = 100*f + 10*(w-f) + 1*(b-w);
    cout << ans << endl;
}
0