#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 "<"<> 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]; } }; // sgn: + -> max, - -> min, 0 -> unweighted template std::vector> weighted_matroid_intersection(int n, Matroid1 M1, Matroid2 M2, std::vector c) { assert(n == (int)c.size()); bool b[n]; std::fill_n(b, n, false); std::vector I[2], p; std::vector> ret(1); for (int u= 0; u < n; u++) I[0].push_back(u); if constexpr (sgn > 0) { auto cmx= *std::max_element(c.begin(), c.end()); for (auto &x: c) x-= cmx; } else { auto cmi= *std::min_element(c.begin(), c.end()); for (auto &x: c) x-= cmi; } for (auto &x: c) x*= sgn * (n + 1); for (bool converged= false; !converged;) { converged= true, M1.build(I[1]), M2.build(I[1]); std::priority_queue> pq; std::vector dist(n, std::numeric_limits::lowest()); for (int u: I[0]) if (M1.oracle(u)) pq.emplace(dist[u]= c[u] - 1, u); for (p.assign(n, -1); pq.size();) { auto [d, u]= pq.top(); if (pq.pop(); d != dist[u]) continue; if (b[u]) { for (int v: I[0]) if (M1.oracle(u, v)) if (cost_t cost= d + c[v] - 1; dist[v] < cost) pq.emplace(dist[v]= cost, v), p[v]= u; } else { if (M2.oracle(u)) { for (int v= u; v != -1; v= p[v]) b[v]= !b[v]; I[0].clear(), I[1].clear(), converged= false; for (int u= 0; u < n; u++) I[b[u]].push_back(u); ret.emplace_back(I[1]); break; } for (int v: I[1]) if (M2.oracle(v, u)) if (cost_t cost= d - c[v] - 1; dist[v] < cost) pq.emplace(dist[v]= cost, v), p[v]= u; } } } return ret; } using namespace std; namespace ALPC_E { // https://atcoder.jp/contests/practice2/tasks/practice2_e int main() { cin.tie(0); ios::sync_with_stdio(false); int N, K; cin >> N >> K; int M= N * N; std::vector w(M); std::vector> parts1(N), parts2(N); std::vector r(N, K); auto edge_id= [N](int i, int j) { return i * N + j; }; auto edge2ij= [N](int e) { return std::make_pair(e / N, e % N); }; for (int i= 0; i < N; i++) for (int j= 0; j < N; j++) { int e= edge_id(i, j); cin >> w[e]; parts1[i].push_back(e); parts2[j].push_back(e); } PartitionMatroid M1(M, parts1, r), M2(M, parts2, r); auto S= weighted_matroid_intersection<+1>(M, M1, M2, w); long long ans= 0; int mi= 0; for (int i= 1, ed= S.size(); i < ed; i++) { long long sum= 0; for (int e: S[i]) sum+= w[e]; if (ans < sum) { ans= sum; mi= i; } } cout << ans << '\n'; vector t(N, string(N, '.')); for (int e: S[mi]) { auto [i, j]= edge2ij(e); t[i][j]= 'X'; } for (int i= 0; i < N; i++) cout << t[i] << '\n'; return 0; } } // namespace ALPC_E namespace atcoder_geocon2013_b { // https://atcoder.jp/contests/geocon2013/tasks/geocon2013_b // |台集合| <= 2500 signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; long long X[N], Y[N]; for (int i= 0; i < N; i++) { cin >> X[i] >> Y[i]; } std::vector> partl(N), partr(N); std::vector w; int e= 0; for (int i= 0; i < N; i++) for (int j= 0; j < N; j++) { if (i != j && X[i] * X[j] > 0) continue; double cost; if (i == j) cost= abs(X[i]); else { double xsum= X[i] + X[j], ydif= Y[i] - Y[j]; cost= sqrt(xsum * xsum + ydif * ydif) / 2; } partl[i].push_back(e), partr[j].push_back(e), w.push_back(cost), ++e; } PartitionMatroid M1(e, partl, vector(N, 1)), M2(e, partr, vector(N, 1)); auto S= weighted_matroid_intersection<-1>(e, M1, M2, w); double ans= 0; for (auto d: S[N]) ans+= w[d]; printf("%.7lf\n", ans); return 0; } } namespace AOJ2429 { // https://onlinejudge.u-aizu.ac.jp/problems/2429 // |台集合| <= 1e4 signed main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; int W[n][n], E[n][n]; for (int i= 0; i < n; ++i) for (int j= 0; j < n; ++j) cin >> W[i][j]; for (int i= 0; i < n; ++i) for (int j= 0; j < n; ++j) cin >> E[i][j]; int m= n * n; vector w(m); vector> partl(n), partr(n); long long mincost= 0; string F[n]; for (int i= 0; i < n; ++i) { cin >> F[i]; int e= i * n; for (int j= 0; j < n; ++j, ++e) { partl[i].push_back(e), partr[j].push_back(e); if (F[i][j] == '.') w[e]= W[i][j]; else w[e]= -E[i][j], mincost+= E[i][j]; } } PartitionMatroid M1(m, partl, vector(n, 1)), M2(m, partr, vector(n, 1)); auto S= weighted_matroid_intersection<-1>(m, M1, M2, w); bool write[n][n]; for (int i= n; i--;) for (int j= n; j--;) write[i][j]= 0; for (auto d: S[n]) mincost+= w[d], write[d / n][d % n]= 1; cout << mincost << '\n'; vector> ans; for (int i= 0; i < n; ++i) for (int j= 0; j < n; ++j) if (write[i][j] ^ (F[i][j] != '.')) ans.emplace_back(i + 1, j + 1, write[i][j] ? "write" : "erase"); cout << ans.size() << '\n'; for (auto [R, C, operate]: ans) cout << R << " " << C << " " << operate << '\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= weighted_matroid_intersection<0>(e, M1, M2, vector(e, 1)).size() - 1; int ans= 100 * x + 10 * (bsize - x) + wsize - bsize; cout << ans << '\n'; return 0; } } // matroid_intersection int main() { cin.tie(0); ios::sync_with_stdio(false); // ALPC_E::main(); // atcoder_geocon2013_b::main(); // AOJ2429::main(); yukicoder421::main(); return 0; }