結果

問題 No.421 しろくろチョコレート
ユーザー yuppe19 😺yuppe19 😺
提出日時 2019-03-14 12:36:31
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,021 bytes
コンパイル時間 1,043 ms
コンパイル使用メモリ 86,444 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-24 14:57:34
合計ジャッジ時間 2,770 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 5 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 4 ms
4,348 KB
testcase_08 AC 3 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 3 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 1 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 6 ms
4,348 KB
testcase_17 AC 10 ms
4,348 KB
testcase_18 AC 13 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 6 ms
4,348 KB
testcase_21 AC 5 ms
4,348 KB
testcase_22 AC 4 ms
4,348 KB
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 AC 2 ms
4,348 KB
testcase_26 AC 2 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 3 ms
4,348 KB
testcase_29 AC 4 ms
4,348 KB
testcase_30 AC 4 ms
4,348 KB
testcase_31 AC 14 ms
4,348 KB
testcase_32 AC 3 ms
4,348 KB
testcase_33 AC 5 ms
4,348 KB
testcase_34 AC 2 ms
4,348 KB
testcase_35 AC 2 ms
4,348 KB
testcase_36 AC 4 ms
4,348 KB
testcase_37 AC 16 ms
4,348 KB
testcase_38 AC 15 ms
4,348 KB
testcase_39 AC 3 ms
4,348 KB
testcase_40 AC 7 ms
4,348 KB
testcase_41 AC 3 ms
4,348 KB
testcase_42 AC 2 ms
4,348 KB
testcase_43 AC 3 ms
4,348 KB
testcase_44 AC 11 ms
4,348 KB
testcase_45 AC 2 ms
4,348 KB
testcase_46 AC 3 ms
4,348 KB
testcase_47 AC 5 ms
4,348 KB
testcase_48 AC 10 ms
4,348 KB
testcase_49 AC 2 ms
4,348 KB
testcase_50 AC 2 ms
4,348 KB
testcase_51 AC 13 ms
4,348 KB
testcase_52 AC 4 ms
4,348 KB
testcase_53 AC 2 ms
4,348 KB
testcase_54 AC 2 ms
4,348 KB
testcase_55 AC 2 ms
4,348 KB
testcase_56 AC 2 ms
4,348 KB
testcase_57 AC 2 ms
4,348 KB
testcase_58 AC 5 ms
4,348 KB
testcase_59 AC 2 ms
4,348 KB
testcase_60 AC 18 ms
4,348 KB
testcase_61 AC 7 ms
4,348 KB
testcase_62 AC 2 ms
4,348 KB
testcase_63 AC 2 ms
4,348 KB
testcase_64 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

struct edge { int to, avail, rev; };

constexpr int inf = 987'654'321;

int R, C, N;
vector<vector<edge>> G;
vector<int> ptr;
vector<bool> used;

void add_edge(int u, int v, int c) {
  G[u].push_back(edge{v, c, ptr[v]++});
  G[v].push_back(edge{u, 0, ptr[u]++});
}

int dfs(int v, int t, int flow) {
  if(v == t) { return flow; }
  used[v] = true;
  for(edge &e : G[v]) {
    edge &x = G[e.to][e.rev];
    if(!used[e.to] && e.avail > 0) {
      int res = dfs(e.to, t, min(e.avail, flow));
      if(res > 0) {
        e.avail -= res;
        x.avail += res;
        return res;
      }
    }
  }
  return 0;
}

int max_flow(int s, int t) {
  int res = 0;
  for(;;) {
    used.assign(N, false);
    int flow = dfs(s, t, inf);
    if(flow == 0) { return res; }
    res += flow;
  }
}

int calc(int r, int c) {
  return r * C + c;
}

int main(void) {
  scanf("%d%d", &R, &C);
  vector<string> F;
  for(int r=0; r<R; ++r) {
    string s; cin >> s;
    F.push_back(s);
  }
  ::N = R*C+2;
  G.assign(N, vector<edge>());
  ptr.assign(N, 0);
  int src = R*C, dst = R*C+1;
  int cntw = 0, cntb = 0;
  for(int r=0; r<R; ++r) {
    for(int c=0; c<C; ++c) {
      int id = calc(r, c);
      switch(F[r][c]) {
        case 'w':
          ++cntw;
          add_edge(src, id, 1);
          for(int dr : {-1, 0, 1}) {
            for(int dc : {-1, 0, 1}) {
              if(dr == 0 && dc == 0) { continue; }
              int nr = r + dr,
                  nc = c + dc;
              if(!(0 <= nr && nr < R && 0 <= nc && nc < C)) { continue; }
              if(F[nr][nc] == 'b') { add_edge(id, calc(nr, nc), 1); }
            }
          }
          break;
        case 'b':
          ++cntb;
          add_edge(id, dst, 1);
          break;
      }
    }
  }
  int maxi = max_flow(src, dst);
  cntw -= maxi;
  cntb -= maxi;
  int pairs = min(cntw, cntb);
  cntw -= pairs;
  cntb -= pairs;
  int res = maxi * 100 + pairs * 10 + cntw + cntb;
  printf("%d\n", res);
  return 0;
}
0