結果

問題 No.421 しろくろチョコレート
ユーザー 小指が強い人
提出日時 2016-09-20 02:10:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,036 bytes
コンパイル時間 2,095 ms
コンパイル使用メモリ 182,500 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-23 07:09:16
合計ジャッジ時間 3,722 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<string> vecs;
template<class T,class U> using Hash=unordered_map<T,U>;
 
#define REP(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define RREP(i, a, n) for(ll i = n-1; i >= (ll)(a); i--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define MD 1000000007
#define _SPLIT " "
 
template<class T> T read(){T a;cin >> a;return a;}
template<class T> void read(T& a){cin >> a;}
template<class T,class ...Args> void read(T& a, Args&... args){cin >> a; read(args...);} 
template<class T> void rarr(T a, int n){for(int i = 0; i < n; i++) {cin >> a[i];}}
template<class T> void write(T a){cout << setprecision(12) << a << endl;}
template<class T,class ...Args> void write(T a, Args... args){cout << setprecision(12) << a << _SPLIT; write(args...);}
template<class T> void warr(vector<T> a, const char* c = " "){cout << a[0];for(int i = 1; i < (int)a.size(); i++)cout << c << a[i];cout << endl;;}
template<class T> void warr(T a, int n, const char* c = " "){cout << a[0];for(int i = 1; i < n; i++)cout << c << a[i];cout << endl;}
void split(string s, string delim, veci& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find
    (delim, pos);if(p == string::npos){result.push_back(atoi(s.substr(pos).data()));break;}else {result.push_back(atoi(s.substr(pos, p - pos).data
    ()));}pos = p + delim.size();}}
void split(string s, string delim, vecs& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find
    (delim, pos);if(p == string::npos){result.push_back(s.substr(pos));break;}else {result.push_back(s.substr(pos, p - pos));}pos = p + delim.size
    ();}}
ll gcd(ll a, ll b){while(true){ll k = a % b;if(k == 0)return b;a = b;b = k;}}
ll comb(ll n, ll m){ll p=1;m=min(m,n-m);for(ll i=1;i<=m;i++){p*=n-i+1;p/=i;}return p;}
typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight=1) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
bool augment(const Graph& g, int u,
    vector<int>& matchTo, vector<bool>& visited) {
  if (u < 0) return true;
  for(auto& e:g[u]) if (!visited[e.dst]) {
    visited[e.dst] = true;
    if (augment(g, matchTo[e.dst], matchTo, visited)) {
      matchTo[e.src] = e.dst;
      matchTo[e.dst] = e.src;
      return true;
    }
  }
  return false;
}
int bipartiteMatching(const Graph& g, int L, Edges& matching) {
  const int n = g.size();
  vector<int> matchTo(n, -1);
  int match = 0;
  rep(u, L) {
    vector<bool> visited(n);
    if (augment(g, u, matchTo, visited)) ++match;
  }
  rep(u, L) if (matchTo[u] >= 0) // make explicit matching
    matching.push_back( Edge(u, matchTo[u]) );
  return match;
}
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int main(void)
{
    int n,m;
    string s[50];
    int sn[50][50]={0};
    read(n,m);
    rarr(s,n);
    int sw=0,sb=0;
    rep(i,n)rep(j,m){
        if(s[i][j]=='w')sn[i][j]=sw++;
    }
    rep(i,n)rep(j,m){
        if(s[i][j]=='b')sn[i][j]=sw+sb,sb++;
    }
    Graph g(sw+sb);
    rep(i,n)rep(j,m){
        if(s[i][j]=='.')continue;
        int src=sn[i][j];
        char c=s[i][j];
        rep(k,4){
            int cx=j+dx[k];
            int cy=i+dy[k];
            if(cx<0||cx>=m||cy<0||cy>=n)continue;
            if(s[cy][cx]=='.'||s[cy][cx]==c)continue;
            g[src].push_back(Edge(src,sn[cy][cx]));
        }
    }
    Edges t;
    int res=0;
    int m_num=bipartiteMatching(g,sw,t);
    sw-=m_num;sb-=m_num;
    res+=m_num*100;
    int cwb=min(sw,sb);
    sw-=cwb;sb-=cwb;
    res+=cwb*10;
    res+=max(sw,sb);
    write(res);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0