#1166358 (C++23) No.421 しろくろチョコレート

• 問題: No.421 しろくろチョコレート
• ユーザー: ZeriToki
• 提出日時: 2026-05-23 16:30:28
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 3,971 bytes
• コンパイル時間: 4,236 ms
• コンパイル使用メモリ: 348,616 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-05-23 16:30:41
• 合計ジャッジ時間: 5,107 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 65

ソースコード

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
struct maxflow{
    struct edge{int to;long long cap;int rev;};
    vector<vector<edge>>G;
    vector<int>level;
    vector<int>iter;
    int n;
    long long last_flow;
    maxflow(int N){
        n=N;
        last_flow=0;
        G.resize(N);
        level.resize(N);
        iter.resize(N);
    }
    void add_edge(int from,int to,long long cap){
        G[from].push_back((edge){to,cap,(int)G[to].size()});
        G[to].push_back((edge){from,0,(int)G[from].size()-1});
    }

    void get_edge(){
        for(int i=0;i<n;i++){
            for(int j=0;j<(int)G[i].size();j++){
                cout<<i<<" "<<G[i][j].to<<" "<<G[i][j].cap<<endl;
            }   
        }
        return;
    }

    void bfs(int s){
        level.assign(n,-1);
        queue<int>que;
        level[s]=0;
        que.push(s);
        while(!que.empty()){
            int v=que.front();
            que.pop();
            for(int i=0;i<(int)G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap>0 && level[e.to]<0){
                    level[e.to]=level[v]+1;
                    que.push(e.to);
                }
            }
        }
    }
    long long dfs(int v,int t,long long f){
        if(v==t) return f;
        for(int &i=iter[v];i<(int)G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0 && level[v]<level[e.to]){
                long long d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0LL;
    }
    long long flow(int s,int t){
        long long flow=0;
        for(;;){
            bfs(s);
            if(level[t]<0){
                last_flow+=flow;
                return last_flow;
            }
            iter.assign(n,0);
            long long f;
            while((f=dfs(s,t,LONG_LONG_MAX))>0){
                flow+=f;
            }
        }
    }
    vector<bool>min_cut(int s){
        vector<bool>res;
        res.assign(n,0);
        queue<int>que;
        que.push(s);
        while(!que.empty()){
            int pos=que.front();
            que.pop();
            res[pos]=true;
            for(edge &nex:G[pos]){
                if(res[nex.to]) continue;
                if(nex.cap>0) que.push(nex.to);
            }
        }
        return res;
    }
};
int main(){
    cout.tie()->sync_with_stdio(0);
    cin.tie(0);
    int N,M;cin>>N>>M;
    char S[N+1][M+1];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            cin>>S[i][j];
        }
    }
    auto get_pos=[&](int r,int c){
        return (r-1)*M+c;
    };
    maxflow F(N*M+2);
    const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(S[i][j]=='.') continue;
            if((i+j)&1){
                F.add_edge(get_pos(i,j),N*M+1,1);
                continue;
            }
            else{
                F.add_edge(0,get_pos(i,j),1);
            }
            rep(k,4){
                int nr=i+dx[k],nc=j+dy[k];
                if(nr<=0 || nr>N || nc<=0 || nc>M) continue;
                if(S[nr][nc]!='.'){
                    F.add_edge(get_pos(i,j),get_pos(nr,nc),1);
                }
            }
        }
    }
    int cnt100=F.flow(0,N*M+1);
    int ans=cnt100*100;
    int black=0,white=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            if(S[i][j]=='w') white++;
            if(S[i][j]=='b') black++;
        }
    }
    ans+=10*(min(black,white)-cnt100);
    ans+=abs(black-white);
    cout<<ans<<endl;
}