結果

問題 No.421 しろくろチョコレート
ユーザー vjudge1
提出日時 2025-01-18 16:00:35
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,468 bytes
コンパイル時間 7,355 ms
コンパイル使用メモリ 262,040 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-01-18 16:00:49
合計ジャッジ時間 9,730 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#define sz(x) (signed)(x).size()
#define int long long 
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 = 2e9;
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 * N];
bool bfs(){
    for (int i = 1; i <= T; i++)    dis[i] = inf;
    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){
    //cout << u << " " << sum << endl;
    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;
            edge[i].w -= t, edge[i ^ 1].w += t;
            res += t, sum -= 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] == 'w'){
                for (int i = 0; i < 4; i++){
                    int nx = x + dx[i], ny = y + dy[i];
                    if (!in(nx, ny) || mp[nx][ny] == '.')   continue;
                    add(ID(x, y), ID(nx, ny), 1), add(ID(nx, ny), ID(x, y), 0);
                }
        }
    //for (int u = 1; u <= T; u++)
    //  for (int i = head[u]; i; i = edge[i].nxt)
    //      cout << i << ": " << u << "->" << edge[i].to << " " << edge[i].w << endl; 
    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