結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー rickytheta
提出日時 2016-09-09 22:47:47
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 16 ms / 2,000 ms
コード長 2,295 bytes
コンパイル時間 1,404 ms
コンパイル使用メモリ 163,492 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:05:02
合計ジャッジ時間 3,204 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void add_edge(int, int, int)’:
main.cpp:44:45: warning: narrowing conversion of ‘g[to].std::vector<edge>::size()’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   44 |   g[from].push_back((edge){to,cap,g[to].size()});
      |                                   ~~~~~~~~~~^~
main.cpp:45:47: warning: narrowing conversion of ‘(g[from].std::vector<edge>::size() - 1)’ from ‘std::vector<edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   45 |   g[to].push_back((edge){from,0,g[from].size()-1});
      |                                 ~~~~~~~~~~~~~~^~
main.cpp: In function ‘int main()’:
main.cpp:68:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |   scanf("%d%d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~
main.cpp:69:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |   REP(i,n)scanf("%s",s[i]);
      |           ~~~~~^~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,m;
char s[52][52];

#define N_MAX 2521

struct edge{int to,cap,rev;};
vector<edge> g[N_MAX];
bool used[N_MAX];

void add_edge(int from,int to,int cap){
  g[from].push_back((edge){to,cap,g[to].size()});
  g[to].push_back((edge){from,0,g[from].size()-1});
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  REP(i,g[v].size()){
    edge &e = g[v][i];
    if(!used[e.to]&&e.cap>0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap -= d;
        g[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int d[] = {1,0,-1,0,1};

int main(){
  scanf("%d%d",&n,&m);
  REP(i,n)scanf("%s",s[i]);
  REP(i,n)REP(j,m){
    if(s[i][j]=='.')continue;
    if((i+j)%2==0){
      add_edge(0,i*m+j+2,1);
    }else{
      add_edge(i*m+j+2,1,1);
    }
    REP(k,4){
      int ni = i+d[k];
      int nj = j+d[k+1];
      if(ni<0||nj<0||ni>=n||nj>=m)continue;
      if(s[ni][nj]!='.'){
        if((i+j)%2==0){
          add_edge(i*m+j+2,ni*m+nj+2,1);
        }else{
          add_edge(ni*m+nj+2,i*m+j+2,1);
        }
      }
    }
  }
  // ford-fulkerson
  int flow = 0;
  while(true){
    REP(i,N_MAX)used[i]=false;
    int f = dfs(0,1,1e9);
    if(f==0)break;
    flow += f;
  }
  int b=0,w=0;
  REP(i,n){
    b+=count(s[i],s[i]+m,'b');
    w+=count(s[i],s[i]+m,'w');
  }
  b-=flow;
  w-=flow;
  int ans = flow*100;
  int u = min(b,w);
  ans += u*10;
  b-=u;
  w-=u;
  ans += b+w;
  printf("%d\n",ans);
  return 0;
}
0