結果

問題 No.421 しろくろチョコレート
ユーザー yuppe19 😺
提出日時 2019-03-14 12:36:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,021 bytes
コンパイル時間 1,020 ms
コンパイル使用メモリ 87,292 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:22:50
合計ジャッジ時間 2,716 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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