結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2019-06-12 14:25:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,451 bytes |
コンパイル時間 | 1,935 ms |
コンパイル使用メモリ | 181,132 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-23 07:23:26 |
合計ジャッジ時間 | 3,394 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
#include<bits/stdc++.h>#define debug(x) cerr << #x << ": " << x << '\n'#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'using namespace std;typedef long long ll;typedef unsigned long long ull;typedef vector<ll> vll;const ll INF = LLONG_MAX/2;const ll MOD = 1e9+7;struct bipartiteGraph{int L, R;vector<vector<int>> adj;vector<int> mate;bipartiteGraph(int L, int R) : L(L), R(R), adj(L+R),mate(L+R, -1) { }void add_edge(int u, int v) {adj[u].push_back(v+L);adj[v+L].push_back(u);}int maximum_matching() {vector<int> level(L);function<bool(void)> levelize = [&]() { // BFSqueue<int> Q;for (int u = 0; u < L; ++u) {level[u] = -1;if (mate[u] < 0) {level[u] = 0;Q.push(u);}}while (!Q.empty()) {int u = Q.front(); Q.pop();for (int w: adj[u]) {int v = mate[w];if (v < 0) return true;if (level[v] < 0) {level[v] = level[u] + 1;Q.push(v);}}}return false;};function<bool(int)> augment = [&](int u) { // DFSfor (int w: adj[u]) {int v = mate[w];if (v < 0 || (level[v] > level[u] && augment(v))) {mate[u] = w;mate[w] = u;return true;}}return false;};int match = 0;while (levelize())for (int u = 0; u < L; ++u)if (mate[u] < 0 && augment(u))++match;return match;}int lPartner(int l){return mate[l]-L;}int rPartner(int r){return mate[r+L];}};signed main(){cin.tie(0);ios::sync_with_stdio(false);ll N,M;cin>>N>>M;vector<string> S(N);ll bsize=0,wsize=0;for(ll i=0;i<N;i++){cin>>S[i];for(ll j=0;j<M;j++){bsize += S[i][j]=='b';wsize += S[i][j]=='w';}}bipartiteGraph g(N*M,N*M);for(ll i=0;i<N;i++){for(ll j=0;j<M;j++)if((i+j)&1&&S[i][j]=='b'){if(i>0&&S[i-1][j]=='w')g.add_edge(i*M+j,(i-1)*M+j);if(i+1<N&&S[i+1][j]=='w')g.add_edge(i*M+j,(i+1)*M+j);if(j>0&&S[i][j-1]=='w')g.add_edge(i*M+j,i*M+j-1);if(j+1<M&&S[i][j+1]=='w')g.add_edge(i*M+j,i*M+j+1);}}ll x=g.maximum_matching();if(bsize>wsize)swap(bsize,wsize);ll ans = 100*x+10*(bsize-x)+wsize-bsize;cout<<ans<<endl;return 0;}