結果

問題 No.421 しろくろチョコレート
ユーザー kkk
提出日時 2024-12-04 18:41:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 3,845 bytes
コンパイル時間 1,121 ms
コンパイル使用メモリ 92,556 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-04 18:41:18
合計ジャッジ時間 2,948 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <vector>
#include <queue>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, S, E) for(int i=(S); i<(E); i++)
struct Edge{
    int to;
    int cap;
    int rev;
};
struct Dinic{
    
    vector<vector<Edge>> G;
    vector<int> levels;
    vector<int> iters;
    const long long INF = 1<<30;
    int n;
    
    Dinic(){ ; }
    Dinic(int _n){
        G.reserve(_n);
        levels.resize(_n, 0);
        iters.resize(_n, 0);
        n = _n;
    }
    
    void set_graph(int from, int to, int cap){
        Edge e = {to, cap, (int)G[to].size()};
        G[from].emplace_back(e);
        e = {from, 0, (int)G[from].size()-1};
        G[to].emplace_back(e);
        return;
    }
    
    void bfs(int s){
        fill(levels.begin(), levels.end(), -1);
        queue<int> Q;
        Q.push(s);
        levels[s] = 0;
        
        while (!Q.empty()){
            int v = Q.front();
            Q.pop();
            
            for (Edge& e : G[v]){
                
                if (e.cap > 0 && levels[e.to] < 0){
                    levels[e.to] = levels[v] + 1;
                    Q.push(e.to);
                }
            }
        }
        
        return;
    }
    
    int dfs(int v, int t, int f){
        if (v == t){
            return f;
        }
        
        for (int& i=iters[v]; i<G[v].size(); i++){
            Edge& e = G[v][i];
            if (e.cap > 0 && levels[e.to] > levels[v]){
                int _f = dfs(e.to, t, min(f, e.cap));
                if (_f > 0){
                    e.cap -= _f;
                    G[e.to][e.rev].cap += _f;
                    return _f;
                }
            }
        }
        
        return 0;
    }
    
    int execute(int s, int t){
        int flow = 0;
        
        while(true){
            bfs(s);
            
            if(levels[t] < 0){
                return flow;
            }
            
            fill(iters.begin(), iters.end(), 0);
            
            while(true){
                int f = dfs(s, t, INF);
                if (f > 0){
                    flow +=  f;
                }else{
                    break;
                }
            }
            
        }
        return 0;
    }
    
    
    
};
  
int N, M;
char B[50][50];
bool isin(int x, int y){
    if (0 <= x && x < N){
        if (0 <= y && y < M){
            return true;
        }
    }
    return false;
}
int main() {
    cin >> N >> M;
    rep(i, 0, N){
        rep(j, 0, M){
            cin >> B[i][j];
        }
    }
    
    Dinic dinic(N*M+2);
    
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int w_cnt = 0, b_cnt = 0;
    
    rep(i, 0, N){
        rep(j, 0, M){
            if (B[i][j] != '.'){
                
                if ((i%2==0 && j%2==0) || (i%2==1 && j%2==1)){
                    w_cnt++;
                    dinic.set_graph(N*M, M*i+j, 1);
                    
                    rep(k, 0, 4){
                        if (isin(i+dy[k], j+dx[k])){
                            if (B[i+dy[k]][j+dx[k]] != '.'){
                                int from = M * i + j;
                                int to = M * (i+dy[k]) + (j+dx[k]);
                                dinic.set_graph(from, to, 1);
                            }
                        }
                    }
                    
                }else{
                    b_cnt++;
                    dinic.set_graph(M*i+j, N*M+1, 1);
                }
            }
        }
    }
    
    int f = dinic.execute(N*M, N*M+1);
    
    int answer = 100 * f;
    w_cnt -= f; b_cnt -= f;
    
    while (w_cnt && b_cnt){
        answer += 10;
        w_cnt--; b_cnt--;
    }
    
    if (w_cnt + b_cnt > 0) answer += (w_cnt + b_cnt);
    
    cout << answer << endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0