#include // clang-format off // std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} // std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} // std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<std::ostream &operator<<(std::ostream&os,const std::pair&x){return os<<"("<std::ostream &operator<<(std::ostream&os,const std::vector&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<std::ostream &operator<<(std::ostream&os,const std::set&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<std::ostream&operator<<(std::ostream &os,const std::array &arr) {os<<'['<void print(std::ostream&os,const Tup &x,std::index_sequence){(void)(int[]){(os<(x)<<", ",0)...};} templatestd::ostream &operator<<(std::ostream&os,const std::tuple &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence());return os<(x)<<")";} const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m"; #define func_LINE_FILE NORMAL_FAINT<<" in "<"< std::vector matroid_intersection(int n, Matroid1 M1, Matroid2 M2) { std::vector b(n, false), pre(n), I[2]; for (int e= 0; e < n; e++) I[0].push_back(e); M1.build(I[1]), M2.build(I[1]); for (bool converged= false; !converged;) { pre.assign(n, false); std::vector L(1, std::vector()); for (int u: I[0]) if (M1.oracle(u)) pre[u]= true, L[0].push_back(u); int m= 0; for (; L.back().size(); m+= 2) { L.push_back({}); for (int e: L[m]) { if (converged= M2.oracle(e)) break; for (int f: I[1]) if (!pre[f] && M2.oracle(f, e)) L[m + 1].push_back(f), pre[f]= true; } if (converged) break; L.push_back({}); for (int e: L[m + 1]) for (int f: I[0]) if (!pre[f] && M1.oracle(e, f)) L[m + 2].push_back(f), pre[f]= true; } if (!converged) break; std::vector> L2(m + 1); for (int e: L[m]) if (M2.oracle(e)) L2[m].push_back(e); for (int i= m; i; i-= 2) { for (int e: L[i - 1]) for (int f: L2[i]) if (M1.oracle(e, f)) { L2[i - 1].push_back(e); break; } for (int e: L[i - 2]) for (int f: L2[i - 1]) if (M2.oracle(f, e)) { L2[i - 2].push_back(e); break; } } pre.assign(n, -1); for (int e: L2[0]) if (M1.oracle(e)) { bool isok= false; if (m) { std::vector ei(m); for (int i= 0; e != -1;) { if (ei[i] == L2[i + 1].size()) e= pre[e], ei[i--]= 0; else if (int f= L2[i + 1][ei[i]++]; pre[f] == -1 && (i & 1 ? M1.oracle(e, f) : M2.oracle(f, e))) if (pre[f]= e, e= f; ++i == m) { if (M2.oracle(e)) for (isok= true; e != -1; e= pre[e]) b[e]= !b[e]; else e= pre[e], --i; } } } else if (M2.oracle(e)) isok= true, b[e]= 1; if (isok) { converged= false, I[0].clear(), I[1].clear(); for (int u= 0; u < n; u++) I[b[u]].push_back(u); M1.build(I[1]), M2.build(I[1]); } } } return I[1]; } class GraphicMatroid { int n; std::vector> es; std::vector g, pos, comp, in, out; inline bool is_ancestor(int u, int v) const { return in[u] <= in[v] && in[v] < out[u]; } public: GraphicMatroid(int n_): n(n_), comp(n), in(n), out(n) {} void add_edge(int u, int v) { es.push_back({u, v}); } void build(const std::vector &I) { in.assign(n, -1), g.resize(I.size() * 2), pos.assign(n + 1, 0); for (int e: I) { auto [u, v]= es[e]; ++pos[u], ++pos[v]; } for (int i= 0; i < n; ++i) pos[i + 1]+= pos[i]; for (int e: I) { auto [u, v]= es[e]; g[--pos[u]]= v, g[--pos[v]]= u; } std::vector ei(pos.begin(), pos.begin() + n), pre(n, -1); for (int u= 0, t= 0, p; u < n; u++) if (in[u] == -1) for (in [comp[u]= p= u]= t++; p >= 0;) { if (ei[p] == pos[p + 1]) out[p]= t, p= pre[p]; else if (int v= g[ei[p]++]; in[v] == -1) comp[v]= comp[u], pre[v]= p, in[p= v]= t++; } } inline bool oracle(int e) const { return comp[es[e][0]] != comp[es[e][1]]; } inline bool oracle(int e, int f) const { if (oracle(f)) return true; return e= es[e][in[es[e][0]] < in[es[e][1]]], is_ancestor(e, es[f][0]) != is_ancestor(e, es[f][1]); } }; struct PartitionMatroid { std::vector belong, R, cnt; PartitionMatroid(int m_, const std::vector> &parts, const std::vector &R_): belong(m_, -1), R(R_) { assert(parts.size() == R.size()); for (int i= parts.size(); i--;) for (int e: parts[i]) belong[e]= i; } void build(const std::vector &I) { cnt= R; for (int e: I) if (belong[e] != -1) cnt[belong[e]]--; } inline bool oracle(int e) const { return belong[e] == -1 || cnt[belong[e]] > 0; } inline bool oracle(int e, int f) const { return oracle(f) || belong[e] == belong[f]; } }; namespace beecrowd2128 { // https://www.beecrowd.com.br/judge/en/problems/view/2128 int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m, k; for (int cnt= 1; cin >> n >> m >> k; cnt++) { cout << "Instancia " << cnt << '\n'; GraphicMatroid M1(n); vector> parts(k); for (int i= 0; i < m; i++) { int u, v, c; cin >> u >> v >> c; M1.add_edge(--u, --v); parts[--c].push_back(i); } PartitionMatroid M2(m, parts, vector(k, 1)); auto S= matroid_intersection(m, M1, M2); cout << (S.size() == n - 1 ? "sim" : "nao") << "\n\n"; } return 0; } } namespace AOJ1163 { // https://onlinejudge.u-aizu.ac.jp/problems/1163 signed main() { cin.tie(0); ios::sync_with_stdio(0); for (int m, n; cin >> m >> n && m;) { int b[m], r[n]; for (int i= 0; i < m; ++i) cin >> b[i]; for (int i= 0; i < n; ++i) cin >> r[i]; vector> partl(m), partr(n); int e= 0; for (int i= 0; i < m; ++i) for (int j= 0; j < n; ++j) if (gcd(b[i], r[j]) > 1) partl[i].push_back(e), partr[j].push_back(e), ++e; PartitionMatroid M1(e, partl, vector(m, 1)), M2(e, partr, vector(n, 1)); auto S= matroid_intersection(e, M1, M2); cout << S.size() << '\n'; } return 0; } } namespace AOJ_GRL7A { // https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/7/GRL_7_A signed main() { cin.tie(0); ios::sync_with_stdio(0); int L, R, M; cin >> L >> R >> M; vector> partl(L), partr(R); for (int i= 0; i < M; i++) { int a, b; cin >> a >> b; partl[a].push_back(i), partr[b].push_back(i); } PartitionMatroid M1(M, partl, vector(L, 1)), M2(M, partr, vector(R, 1)); auto S= matroid_intersection(M, M1, M2); cout << S.size() << '\n'; return 0; } } namespace yukicoder421 { signed main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector S(N); int bsize= 0, wsize= 0; for (int i= 0; i < N; i++) { cin >> S[i]; for (int j= 0; j < M; j++) bsize+= S[i][j] == 'b', wsize+= S[i][j] == 'w'; } vector> partl(N * M), partr(N * M); int e= 0; auto add_edge= [&](int l, int r) { partl[l].push_back(e), partr[r].push_back(e), ++e; }; for (int i= 0; i < N; i++) { for (int j= 0; j < M; j++) if ((i + j) & 1 && S[i][j] == 'b') { if (i > 0 && S[i - 1][j] == 'w') add_edge(i * M + j, (i - 1) * M + j); if (i + 1 < N && S[i + 1][j] == 'w') add_edge(i * M + j, (i + 1) * M + j); if (j > 0 && S[i][j - 1] == 'w') add_edge(i * M + j, i * M + j - 1); if (j + 1 < M && S[i][j + 1] == 'w') add_edge(i * M + j, i * M + j + 1); } } if (bsize > wsize) swap(bsize, wsize); PartitionMatroid M1(e, partl, vector(N * M, 1)), M2(e, partr, vector(N * M, 1)); int x= matroid_intersection(e, M1, M2).size(); int ans= 100 * x + 10 * (bsize - x) + wsize - bsize; cout << ans << '\n'; return 0; } } int main() { cin.tie(0); ios::sync_with_stdio(false); // beecrowd2128::main(); // AOJ1163::main(); // AOJ_GRL7A::main(); yukicoder421::main(); return 0; }