結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 はまやんはまやん
|
| 提出日時 | 2017-05-09 12:53:56 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 8,176 bytes |
| コンパイル時間 | 2,101 ms |
| コンパイル使用メモリ | 187,372 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-23 07:15:24 |
| 合計ジャッジ時間 | 3,690 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 65 |
ソースコード
/* ``` `. ` .g,`Welcome To My Coding Space! .MMe `(F(#~ `.J,`.M/7b. dD.N; (#=#:`` db (m.#` Wl(@ jF ``` ` ` ` ..+kMMN;_(Y> `(TD d$..gHN_` `` ...... ` ` ` `..gMB61+1+dK `- `. .TM@^(d%`` `` ..JggHHMMHHYYTHMMMNmgJ.. .kB6z?1+z1+<dD ..` . ``.` `.V'``..+HMBYC1?1+???=?====????1vTHMNe+1+dMB"BMMM% .`je. `.. ..+@``..gM9C1+?==??==?==?=?===??=??=?1?zTMNeJTHg..``...`.,S._`.` d$ `` ` .(kBY1+==????=?=??=?=??=???=?=?=?=????+zTMm+?TMm.. ` d[ .``.M}`.(M9++?=????==???=?=??=?=?=?=?=?=?=?===?==1+7Mmx?MN,``..._^`.. (F `` ` ` ` ` ` (M8++z11==?==??==??=?==?=?=?==??=??=??==??==?=+7Mm<dNg, ` .`.. (#! `` ` ..(JgH@MMMMMMB1+=??=??=?????==11??1=1?1?=1+=11?1==?=1=??=??11+WNJdMt .``.` J#! `.(HHYYC?1+??z>+H8+=??=?=?=???=?=?=z1&z1?==?1<dNs111?==1ux?==?=?==1zdNcW% ..`. J#~``.WNx<?1?==1=zdMD+=?==?===?=?==?===<dNNx1z??==+WMN+g&&&xdMk1??=1===???MN}`.`.`. J#` `` ?MNc1=1?z?jH8+==?=?==??=jQ21=?=?(M$?WNx<1=zudMMMszOCvTHMmx+?1?z+1?zd#:..`.`. J@ ``` .M81==?==>dM<??===?=?=?+dNy+?=?jM@ ` ?WNe+zO>dNcHmJ1+1JMMR1?z??Ne1<d#~.`..`. dF(M3+1+?==?jMD+=?z1&&?v1+jMMb+=?1d#!`..``?HNx+?+HR ?Mm+1<dMMp?==<dNc<d#_.`..`.`dF `,MHmax111=<dNC?=?=(M#ugH9M#W#6+?(M'`.`.... ?WNe<dM: .TNm<dN?Nm<=zzMR+M@` .``.. dF `` `` _CM$+??1d#<==?=>dM9+?(MF(MI+jMf .`.``.`.. (TNaHr`.`.TNmN:(MR+?zMK(M$` `.`.``dF `J#<=1<jME+1?=1d9Mn1<jN! qN(d@_.`..`.`.`.```-7Y5.....,TB! (MmJ+MH(M: ...`.`.d$`` .M$iggWWMR+1?<dDjMNxjMB .NgN``..``.`.``....`.d#Y"""YWNg. .WNxW#J@ .`.`.``.H: `_Y""! .M$jm+?1zd#TNzM}.. ?M% .`..`.`..``.`.. .+NMNg,.?Mm._ ?NMNM$ ..`..``.# `.HPj#z=?<d#_WM#:.JgHH6 . `.`.`..``.`.`jMMF`.MMN..TN, ?@jM}`..`.`.`JD `` ` dbjMI?=+MF`.7XME^_.--,. ..`.``.`..`.`.M#XNgjNdMR. ?N-. (#~``.``.. d%` d#<WR1z(Mt` (#' (MMBTHNe.`..`..`.`.` .M#UMMMM#W#_. zN. dF`.`...`..H} `?MO(N+?jM:`.M!`.M9N+.-MMR `..`..`.`.`_?MmTMMMwM#~...H: .H}`..`..` (#`` ` ` WNJMR<dN_ JB dNwMMMMNdM[`.`.`.`.`.. ,TNNggMB! .` ~ `(M `.`.``. dF`.MdMNoW@ `JP `(MKdMMNMdM}`.`..`.`.`.... .??!`.`.`..`..dD .`....`.W'?MMMMMP `(R`..?MmyUWQMB ..`..`.`.`..`..`..`.`.`_`-.gM#!.`.``.``.@` `` _7NTMN.`.H/`. ,TMMB"! .``.`.`..`.``.``.`..`.`. .,NIdb` .`..` j$` Wm.M;`._!..`.`...`_`...``.. ...(+ga,`.....``(NjMr`..`... .#:.MpdN_.`. ``.``.`..`..(-JggkWY9YC<>;?Wp .``.` J#>dN, ..``.`dF``_UmMn .`..`..`..`. JMYT1<;;;>>>>>;>>?Wo ..`. dK1=dN,`..``.MN+.dMMe .`.``.`.`.` d#<;>>>>;>>>>;>>>>(N,`.. -MK1llvWm. JM?Mp. ` `` .M9+?Me`.`..`.`.`` JN(>;>>;>>;>>>;>>><db` (kH5lllllzXMm.-NNszWm ` `` (#1+???Hm, ..`..`..`(N:>>>>>;>>>>>;>>><d@_.JNZIlllllllzvTWB6zlJMp `` `` j@1+==?1zvHm.`...`....Hc<>>>>>>>>>>>>><(W$(M8TIllllllllllllllllzvMo ` ` `(#1?==1?===z?TNa,.` `` (Ne<<>>>>><;><;jgMMY1HK1lllllllllllllllllllJMp `.Ne&g&x1=?=?==?1zTHNmJ-...dNgJ++++&ggMH9=~ .M9Izlllllllllllllllllll1WF `` _???MK<=??=??1z?(MM@!d#M#Y""""=<!!~``` .d8Illllllll=lll=lllllllzudY ` `` dH<?+uev?=1uMM^ d@vN&.`...`.`.`.-JH91zzl=llllllllllll=lzllzd#' ` `,MNMBHNIvjdB(D ` d#=zTNm.....JgHM9Izlllludk=zl=ll=llllllvug#^` ` `.MmgM=+M$ ` d#zzO1vUUUU9TI=lllzzO1dKT#zOlllll=llll=dM=` `(Y^ JBdr ` dNmxzIlllllllllllz1ug#= .My1llllllllllzdD `` j@1dR ``(#~THaxl=lzzlzzzugW"!` ``,Nzlzz=lllllzd#: `` ` .#z=d# ``(#_` .7THWQkWHB"^ ` ` ` ?NsIzzlll=ljM\` `` (M6zldN_` .M| ` `` ` .WezllzllzH% `` `` ` .+#Czl=dM;` dR ` 4m+zll1dD` `.d@1llzvdMb ,# ` ` ?Wmxzdf */#include<bits/stdc++.h>#define rep(i,a,b) for(int i=a;i<b;i++)using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }//---------------------------------------------------------------------------------------------------template<class V> struct MaxFlow {struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };int MV; vector<vector<edge>> E; vector<int> itr, lev;MaxFlow() {} MaxFlow(int n) { init(n); }void init(int n) { MV = n; itr = vector<int>(MV), lev = vector<int>(MV); E = vector<vector<edge>>(MV); }void add_edge(int x, int y, V cap, bool undir = false) { E[x].push_back(edge(y, (int)E[y].size(), cap));E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0)); }void bfs(int cur) { rep(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);while (q.size()) { int v = q.front(); q.pop();for(auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to); } }V dfs(int from, int to, V cf) { if (from == to) return cf;for (; itr[from]<E[from].size(); itr[from]++) {edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) {V f = dfs(e->to, to, min(cf, e->cap));if (f>0) { e->cap -= f; E[e->to][e->reve].cap += f; return f; }} } return 0; }V maxflow(int from, int to) { V fl = 0, tf;while (1) { bfs(from); if (lev[to]<0) return fl;rep(i, 0, MV) itr[i] = 0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;}}};struct BipartiteMatching {int N, M; MaxFlow<int> mf;BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); }void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); }int match() {rep(a, 0, N) mf.add_edge(N + M, a, 1);rep(b, 0, M) mf.add_edge(N + b, N + M + 1, 1);return mf.maxflow(N + M, N + M + 1); }int whois(int a) { // マッチング相手を返す(無いなら-1)for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N;return -1;}};//---------------------------------------------------------------------------------------------------int H, W;string S[50];int dx[4] = { 0, 1, 0, -1 };int dy[4] = { -1, 0, 1, 0 };//---------------------------------------------------------------------------------------------------void _main() {cin >> H >> W;rep(i, 0, H) cin >> S[i];vector<int> b, w;rep(y, 0, H) rep(x, 0, W) {if (S[y][x] == 'b') b.push_back(y * W + x);if (S[y][x] == 'w') w.push_back(y * W + x);}sort(b.begin(), b.end());sort(w.begin(), w.end());BipartiteMatching bm(b.size(), w.size());rep(y, 0, H) rep(x, 0, W) if(S[y][x] == 'b'){rep(i, 0, 4) {int xx = x + dx[i];int yy = y + dy[i];if (xx < 0 || W <= xx) continue;if (yy < 0 || H <= yy) continue;if (S[yy][xx] != 'w') continue;int bb = lower_bound(b.begin(), b.end(), y * W + x) - b.begin();int ww = lower_bound(w.begin(), w.end(), yy * W + xx) - w.begin();bm.add_edge(bb, ww);}}int p100 = bm.match();int rb = b.size() - p100;int rw = w.size() - p100;int p10 = min(rb, rw);int ans = 100 * p100 + 10 * p10 + (b.size() - p100 - p10) + (w.size() - p100 - p10);cout << ans << endl;}