結果

問題 No.421 しろくろチョコレート
ユーザー pngnpngn
提出日時 2019-09-02 23:14:05
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 12,223 bytes
コンパイル時間 778 ms
コンパイル使用メモリ 89,996 KB
最終ジャッジ日時 2023-10-24 14:59:31
合計ジャッジ時間 1,165 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In constructor ‘PrimalDual<flow_t, cost_t>::PrimalDual(int)’:
main.cpp:406:37: error: ‘numeric_limits’ was not declared in this scope
  406 |   PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
      |                                     ^~~~~~~~~~~~~~
main.cpp:406:60: error: expected primary-expression before ‘>’ token
  406 |   PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
      |                                                            ^
main.cpp:406:66: error: no matching function for call to ‘max()’
  406 |   PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
      |                                                             ~~~~~^~
In file included from /usr/include/c++/11/vector:60,
                 from main.cpp:2:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
main.cpp:406:66: note:   candidate expects 2 arguments, 0 provided
  406 |   PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
      |                                                             ~~~~~^~
In file included from /usr/include/c++/11/vector:60,
                 from main.cpp:2:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
main.cpp:406:66: note:   candidate expects 3 arguments, 0 provided
  406 |   PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
      |                                                             ~~~

ソースコード

diff # 

#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<unordered_map>
#include<stack>
#include<string>
#include<algorithm>
#include<functional>
#include<cstring>
#include<complex>
#include<bitset>
#include<iostream>
#include<cassert>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> Q;
typedef complex<double> C;
#define cx real()
#define cy imag()
const ll INF = 1LL << 60;
const double DINF = 1e30;
const ll mod = 1000000007;
const ll dx[4] = {1, 0, -1, 0};
const ll dy[4] = {0, -1, 0, 1};
const C I = C(0, 1);
const double EPS = 1e-10;
const ll NCK_MAX = 510000;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

ll extgcd(ll a, ll b, ll& x, ll& y) {
  if (b == 0) {
    x = 1, y = 0; return a;
  }
  ll q = a/b, g = extgcd(b, a - q*b, x, y);
  ll z = x - q * y;
  x = y;
  y = z;
  return g;
}

ll invmod (ll a, ll m) { // a^-1 mod m
  ll x, y;
  extgcd(a, m, x, y);
  x %= m;
  if (x < 0) x += m;
  return x;
}

ll *fac, *finv, *inv;

void nCk_init(ll mod) {
  fac = new ll[NCK_MAX];
  finv = new ll[NCK_MAX];
  inv = new ll[NCK_MAX];
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (ll i = 2; i < NCK_MAX; i++) {
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod%i] * (mod / i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

ll nCk(ll n, ll k, ll mod) {
  if (fac == NULL) nCk_init(mod);
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

template <typename T>
class Zip {
  vector<T> d;
  bool flag;
  void init() {
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    flag = false;
  }
public:
  Zip() {
    flag = false;
  }
  void add(T x) {
    d.push_back(x);
    flag = true;
  }
  ll getNum(T x) {
    if (flag) init();
    return lower_bound(d.begin(), d.end(), x) - d.begin();
  }
  ll size() {
    if (flag) init();
    return (ll)d.size();
  }
};

class UnionFind {
  vector<ll> par, rank; // par > 0: number, par < 0: -par
public:
  void init(ll n) {
    par.resize(n); rank.resize(n);
    fill(par.begin(), par.end(), 1); fill(rank.begin(), rank.end(), 0);
  }
  ll getSize(ll x) {
    return par[find(x)];
  }
  ll find(ll x) {
    if (par[x] > 0) return x;
    return -(par[x] = -find(-par[x]));
  }
  void merge(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) {
      par[y] += par[x];
      par[x] = -y;
    } else {
      par[x] += par[y];
      par[y] = -x;
      if (rank[x] == rank[y]) rank[x]++;
    }
  }
  bool isSame(ll x, ll y) {
    return find(x) == find(y);
  }
};


template <typename T>
class SegmentTree {
  ll n;
  vector<T> node;
  function<T(T, T)> fun, fun2;
  bool customChange;
  T outValue, initValue;
public:
  void init(ll num, function<T(T, T)> resultFunction, T init, T out, function<T(T, T)> changeFunction = NULL) {
    // changeFunction: (input, beforevalue) => newvalue
    fun = resultFunction;
    fun2 = changeFunction;
    customChange = changeFunction != NULL;
    n = 1;
    while (n < num) n *= 2;
    node.resize(2 * n - 1);
    fill(node.begin(), node.end(), init);
    outValue = out;
    initValue = init;
  }
  void valueChange(ll num, T value) {
    num += n-1;
    if (customChange) node[num] = fun2(value, node[num]);
    else node[num] = value;
    while (num > 0) num = (num - 1) / 2, node[num] = fun(node[num * 2 + 1], node[num * 2 + 2]);
  }
  T rangeQuery(ll a, ll b, ll l = 0, ll r = -1, ll k = 0) { // [a, b)
    if (r == -1) r = n;
    if (a <= l && r <= b) return node[k];
    if (b <= l || r <= a) return outValue;
    ll mid = (l + r) / 2;
    return fun(rangeQuery(a, b, l, mid, 2*k+1), rangeQuery(a, b, mid, r, 2*k+2));
  }
};

template <typename T>
class Graph {
  struct edge { ll to; T cost; };
  struct edge_data { ll from, to; T cost; };

  ll v;
  vector<vector<edge>> e, re;
  vector<edge_data> ed;
  vector<bool> used;
  vector<ll> vs, cmp;
  bool isDirected, isMinasEdge;
public:
  Graph(ll _v, bool _isDirected = true) {
    //_v++;
    v = _v, isDirected = _isDirected; isMinasEdge = false;
    e.resize(v), re.resize(v);
  }
  void add_edge(ll s, ll t, T cost = 1) {
    e[s].push_back((edge){t, cost});
    if (!isDirected) e[t].push_back((edge){s, cost});
    else re[t].push_back((edge){s, cost});
    ed.push_back((edge_data){s, t, cost});
    if (cost < 0) isMinasEdge = true;
  }
  vector<T> dijkstra(ll s) {
    vector<T> d(v, INF);
    d[s] = 0;
    auto edge_cmp = [](const edge& a, const edge& b) { return a.cost > b.cost; };
    priority_queue<edge, vector<edge>, decltype(edge_cmp)> pq(edge_cmp);
    pq.push((edge){s, 0});
    while (!pq.empty()) {
      edge temp = pq.top(); pq.pop();
      if (d[temp.to] < temp.cost) continue;
      for (const edge& next : e[temp.to]) {
        T cost = temp.cost + next.cost;
        if (d[next.to] > cost) {
          d[next.to] = cost;
          pq.push((edge){next.to, cost});
        }
      }
    }
    return d;
  }
  vector<T> bellmanford(ll s) {
    vector<T> d(v, INF);
    d[s] = 0;
    for (ll i = 0; i < v; i++) {
      for (const edge_data& temp : ed) {
        if (d[temp.from] != INF && d[temp.to] > d[temp.from] + temp.cost) d[temp.to] = d[temp.from] + temp.cost;
        if (!isDirected && d[temp.to] != INF && d[temp.from] > d[temp.to] + temp.cost) d[temp.from] = d[temp.to] + temp.cost;
      }
    }
    for (ll i = 0; i < v; i++) {
      for (const edge_data& temp : ed) {
        if (d[temp.from] != INF && d[temp.to] > d[temp.from] + temp.cost) d[temp.to] = -INF;
        if (!isDirected && d[temp.to] != INF && d[temp.from] > d[temp.to] + temp.cost) d[temp.from] = -INF;
      }
    }
    return d;
  }
  vector<T> shortest_path(ll s) {
    if (isMinasEdge) return bellmanford(s);
    else return dijkstra(s);
  }
  T kruskal() {
    // if (isDirected)
    UnionFind uf;
    uf.init(v);
    auto edge_data_cmp = [](const edge_data& a, const edge_data& b) { return a.cost < b.cost; };
    sort(ed.begin(), ed.end(), edge_data_cmp);
    T ans = 0;
    for (const edge_data& temp : ed) {
      if (uf.isSame(temp.from, temp.to)) continue;
      uf.merge(temp.from, temp.to);
      ans += temp.cost;
    }
    return ans;
  }
  void scc_dfs(ll s) {
    used[s] = true;
    for (const edge& i : e[s]) if (!used[i.to]) scc_dfs(i.to);
    vs.push_back(s);
  }
  void scc_rdfs(ll s, ll k) {
    used[s] = true;
    cmp[s] = k;
    for (const edge& i : re[s]) if (!used[i.to]) scc_rdfs(i.to, k);
  }
  vector<ll> scc() {
    used.resize(v);
    fill(used.begin(), used.end(), false);
    cmp.resize(v);
    vs.clear();
    for (ll i = 0; i < v; i++) if (!used[i]) scc_dfs(i);
    used.resize(v);
    fill(used.begin(), used.end(), false);
    ll k = 0;
    for (ll i = vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) scc_rdfs(vs[i], k++);
    return cmp;
  }
};

template<typename T>
class Flow {
  struct edge {
    ll to; T cap; ll rev;
  };

  vector<vector<edge> > G;
  vector<ll> level, iter;
  bool isDirected;
public:
  Flow(ll n, bool _isDirected = true) : G(n), level(n), iter(n), isDirected(_isDirected) {}

  void add_edge(ll from, ll to, T cap) {
    G[from].emplace_back((edge){to, cap, (ll)G[to].size()});
    G[to].emplace_back((edge){from, isDirected ? 0LL : cap, (ll)G[from].size()-1});
    //return G[to].back().rev;
  }

  void bfs(ll s) {
    fill(level.begin(), level.end(), -1);
    queue<ll> que;
    level[s] = 0;
    que.emplace(s);
    while (!que.empty()) {
      ll v=que.front(); que.pop();
      for (ll i=0; i < (ll)G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[v]+1;
          que.emplace(e.to);
        }
      }
    }
  }

  T dfs(ll v, ll t, T f) {
    if (v == t) return f;
    for (ll &i = iter[v]; i < (ll)G[v].size(); i++) {
      edge &e = G[v][i];
      if (e.cap > 0 && level[v] < level[e.to]) {
        T d = dfs(e.to, t, min(f, e.cap));
        if (d == 0) continue;
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
    return 0;
  }

  T maxflow(ll s, ll t, T lim = INF) {
    T fl = 0;
    while (1) {
      bfs(s);
      if (level[t] < 0 || lim == 0) break;
      fill(iter.begin(), iter.end(), 0);
      while(1) {
        T f = dfs(s, t, lim);
        if(f == 0) break;
        fl += f;
        lim -= f;
      }
    }
    return fl;
  }
};

class BipartiteMatching {
  vector<ll> pre, root;
  vector<vector<ll>> to;
  vector<ll> p, q;
  ll n, m;
public:
  BipartiteMatching(ll n, ll m) : pre(n, -1), root(n, -1), to(n), p(n, -1), q(m, -1), n(n), m(m){}
  void add_edge(ll a, ll b) { to[a].push_back(b);}
  ll solve() {
    ll res = 0;
    bool upd = true;
    while (upd) {
      upd = false;
      queue<ll> s;
      for (ll i = 0; i < n; ++i) {
        if (!~p[i]) {
          root[i] = i;
          s.push(i);
        }
      }
      while (!s.empty()) {
        ll v = s.front(); s.pop();
        if (~p[root[v]]) continue;
        for (ll i = 0; i < (ll)to[v].size(); ++i) {
          ll u = to[v][i];
          if (!~q[u]) {
            while (~u) {
              q[u] = v;
              swap(p[v],u);
              v = pre[v];
            }
            upd = true;
            ++res;
            break;
          }
          u = q[u];
          if (~pre[u]) continue;
          pre[u] = v; root[u] = root[v];
          s.push(u);
        }
      }
      if (upd) fill(pre.begin(),pre.end(),-1), fill(root.begin(),root.end(),-1);
    }
    return res;
  }
};

template< typename flow_t, typename cost_t >
struct PrimalDual {
  const cost_t INF;

  struct edge {
    int to;
    flow_t cap;
    cost_t cost;
    int rev;
    bool isrev;
  };
  vector< vector< edge > > graph;
  vector< cost_t > potential, min_cost;
  vector< int > prevv, preve;

  PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}

  void add_edge(int from, int to, flow_t cap, cost_t cost) {
    graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false});
    graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true});
  }

  cost_t min_cost_flow(int s, int t, flow_t f) {
    int V = (int) graph.size();
    cost_t ret = 0;
    using Pi = pair< cost_t, int >;
    priority_queue< Pi, vector< Pi >, greater< Pi > > que;
    potential.assign(V, 0);
    preve.assign(V, -1);
    prevv.assign(V, -1);

    while(f > 0) {
      min_cost.assign(V, INF);
      que.emplace(0, s);
      min_cost[s] = 0;
      while(!que.empty()) {
        Pi p = que.top();
        que.pop();
        if(min_cost[p.second] < p.first) continue;
        for(int i = 0; i < graph[p.second].size(); i++) {
          edge &e = graph[p.second][i];
          cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
          if(e.cap > 0 && min_cost[e.to] > nextCost) {
            min_cost[e.to] = nextCost;
            prevv[e.to] = p.second, preve[e.to] = i;
            que.emplace(min_cost[e.to], e.to);
          }
        }
      }
      if(min_cost[t] == INF) return -1;
      for(int v = 0; v < V; v++) potential[v] += min_cost[v];
      flow_t addflow = f;
      for(int v = t; v != s; v = prevv[v]) {
        addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
      }
      f -= addflow;
      ret += addflow * potential[t];
      for(int v = t; v != s; v = prevv[v]) {
        edge &e = graph[prevv[v]][preve[v]];
        e.cap -= addflow;
        graph[v][e.rev].cap += addflow;
      }
    }
    return ret;
  }
};

ll n, m, b, w;
char s[50][51];

int main() {
  scanf("%lld%lld", &n, &m);
  for (ll i = 0; i < n; i++) scanf("%s", s[i]);
  for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) if (s[i][j] == 'w') w++; else if (s[i][j] == 'b') b++;
  BipartiteMatching bm(m*n, m*n);
  for (ll i = 0; i < n; i++) for (ll j = 0; j < m; j++) if (s[i][j] == 'w') {
    for (ll k = 0; k < 4; k++) {
      ll x = i + dx[k], y = j + dy[k];
      if (x < 0 || y < 0 || x == n || y == m) continue;
      if (s[x][y] == 'b') bm.add_edge(i*m+j, x*m+y);
    }
  }
  ll num = bm.solve();
  ll mn = min(b, w) - num;
  printf("%lld\n", 100LL*num + 10 * mn + (max(b, w) - min(b, w)));
}
0