結果

問題 No.421 しろくろチョコレート
ユーザー vjudge1
提出日時 2024-12-22 15:30:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,703 bytes
コンパイル時間 1,813 ms
コンパイル使用メモリ 172,304 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-22 15:30:33
合計ジャッジ時間 6,105 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 38 RE * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#define sz(x) (signed)(x).size()
using namespace std;
 
void file_IO(){
    freopen("chocolate.in", "r", stdin);
    freopen("chocolate.out", "w", stdout);
}
 
const int N = 55;
const int M = 1e5 + 10;
const int inf = 20100705;
int n, m, S, T, cntw, cntb, ans = 0;
char mp[N][N];
 
int tot = 1, head[N * N], cur[N * N];
struct Edge{
    int to, w, nxt;
}edge[M];
void add(int u, int v, int w){
    edge[++tot].to = v;
    edge[tot].w = w;
    edge[tot].nxt = head[u];
    head[u] = tot;
}
int ID(int x, int y){
    return (x - 1) * m + y;
}
bool in(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}
 
int dis[N];
 
bool bfs(){
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0, cur[S] = head[S];
    queue<int> Q = queue<int>(); Q.push(S);
    while (sz(Q)){
        int u = Q.front();
        Q.pop();
        for (int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].to;
            if (edge[i].w > 0 && dis[u] + 1 < dis[v]){
                dis[v] = dis[u] + 1;
                cur[v] = head[v], Q.push(v);
                if (v == T)     return 1;
            }
        }
    }
    return 0;
}
 
int dinic(int u, int sum){
    if (u == T)     return sum;
    int res = 0;
    for (int i = cur[u]; i; i = edge[i].nxt){
        int v = edge[i].to;
        cur[u] = i;
        if (edge[i].w > 0 && dis[v] == dis[u] + 1){
            int t = dinic(v, min(sum, edge[i].w));
            if (!t)     dis[v] = inf;
            res += t, sum -= t;
            edge[i].w -= t, edge[i ^ 1].w += t;
            if (!sum)   break;
        }
    }
    return res;
}
 
signed main(){
    //file_IO();
    cin >> n >> m;
    S = n * m + 1, T = n * m + 2;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            cin >> mp[i][j];
            cntw += (mp[i][j] == 'w' ? 1 : 0);
            cntb += (mp[i][j] == 'b' ? 1 : 0);
            if (mp[i][j] == 'w')
                add(S, ID(i, j), 1), add(ID(i, j), S, 0);
            else if (mp[i][j] == 'b')
                add(ID(i, j), T, 1), add(T, ID(i, j), 0);
        }
    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
            if (mp[x][y] != '.'){
                for (int i : {0, 1, 2, 3}){
                    int nx = x + dx[i], ny = y + dy[i];
                    if (!in(nx, ny) || mp[nx][ny] == '.')   continue;
                    (mp[x][y] == 'w' ? add(ID(x, y), ID(nx, ny), 1) : add(ID(x, y), ID(nx, ny), 0));
                }
            }
    while (bfs())   ans += dinic(S, inf);
    cout << ans * 100 + (min(cntb, cntw) - ans) * 10 + max(cntb, cntw) - min(cntb, cntw) << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0