結果

問題 No.421 しろくろチョコレート
ユーザー hipokaba
提出日時 2016-09-12 02:03:03
言語 C++11
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,764 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 53,716 KB
最終ジャッジ日時 2024-11-14 19:49:20
合計ジャッジ時間 1,211 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:16:1: error: ‘vector’ does not name a type
   16 | vector<E> g[2502];
      | ^~~~~~
main.cpp: In function ‘void add_edge(int, int)’:
main.cpp:24:9: error: ‘g’ was not declared in this scope
   24 |         g[f].push_back({t, 1, (int)g[t].size()});
      |         ^
main.cpp: In function ‘int dfs(int, int, int)’:
main.cpp:64:19: error: ‘g’ was not declared in this scope
   64 |         for(E& e: g[v]){
      |                   ^

ソースコード

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

#include <iostream>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
const int inf = 1e4;
struct E{
    int t, c, r;
};
int n, m;
string s[50];
vector<E> g[2502];
bool u[2502];
int encode(int i, int j){
    return i * m + j;
}
void add_edge(int f, int t){
    g[f].push_back({t, 1, (int)g[t].size()});
    g[t].push_back({f, 0, (int)g[f].size() - 1});
}
void make_graph(){
    rep(i, n){
        rep(j, m){
            if(s[i][j] == 0){
                add_edge(encode(n, 0) ,encode(i, j));
            }
            else if(s[i][j] == 1){
                add_edge(encode(i, j), encode(n, 1));
            }
            if(i + 1 < n && s[i][j] + s[i + 1][j] == 1){
                int p = encode(i, j), q = encode(i + 1, j);
                if(s[i][j] == 0){
                    add_edge(p, q);
                }
                else{
                    add_edge(q, p);
                }
            }
            if(j + 1 < m && s[i][j] + s[i][j + 1] == 1){
                int p = encode(i, j), q = encode(i, j + 1);
                if(s[i][j] == 0){
                    add_edge(p, q);
                }
                else{
                    add_edge(q, p);
                }
            }
        }
    }
}
int dfs(int v, int t, int f){
    if(v == t){
        return f;
    }
    u[v] = true;
    for(E& e: g[v]){
        if(!u[e.t] && e.c > 0){
            int d = dfs(e.t, t, min(f, e.c));
            if(d > 0){
                e.c -= d;
                g[e.t][e.r].c += d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s, int t){
    int mf = 0;
    while(1){
        fill_n(u, n * m + 2, false);
        int f = dfs(s, t, inf);
        if(f == 0){
            return mf;
        }
        mf += f;
    }
}
int main(){
    cin >> n >> m;
    rep(i, n){
        cin >> s[i];
        rep(j, m){
            s[i][j] = s[i][j] != '.' ? s[i][j] == 'w' : 2;
        }
    }
    make_graph();
    int k = max_flow(encode(n, 0), encode(n, 1));
    int b = -k, w = -k;
    rep(i, n){
        rep(j, m){
            if(s[i][j] == 0){
                ++b;
            }
            else if(s[i][j] == 1){
                ++w;
            }
        }
    }
    int l = min(b, w);
    cout << k * 100 + l * 10 + (b + w - 2 * l) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0