제출 #682088

#제출 시각아이디문제언어결과실행 시간메모리
682088etheningDango Maker (JOI18_dango_maker)C++17
33 / 100
272 ms262144 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; // RGW int n, m; string s[3005]; int a[3005][3005]; int cnt, cnt2; template<class T> struct dinic { static constexpr T INF = numeric_limits<T>::max(); struct edge { int v, r; T c; edge(int _v, int _r, T _c) : v{_v}, r{_r}, c{_c} {} }; int n, s, t; vector<vector<edge>> G; vector<int> d, arc; dinic(int _n, int _s, int _t) : n{_n}, s{_s}, t{_t}, G(_n) {} void add_edge(int u, int v, T c) { G[u].emplace_back(v, (int)G[v].size(), c); G[v].emplace_back(u, (int)G[u].size() - 1, 0); } int bfs() { d.assign(n, 0), arc.assign(n, 0); queue<int> q; d[s] = 1, q.emplace(s); while (!q.empty()) { int u = q.front(); q.pop(); for (auto [v, r, c] : G[u]) { if (!d[v] && c) { d[v] = d[u] + 1; if (v == t) return 1; q.emplace(v); } } } return d[t]; } T dfs(int u, T f) { if (u == t) return f; T sum = 0; for (int& i = arc[u]; i < (int)G[u].size(); ++i) { auto& [v, r, c] = G[u][i]; if (d[v] == d[u] + 1 && c) { T res = dfs(v, min(f, c)); if (res) { c -= res, G[v][r].c += res; sum += res, f -= res; if (!f) return sum; } else { d[v] = 0; } } } return sum; } T max_flow() { T sum = 0; while (bfs()) { while (T res = dfs(s, INF)) { sum += res; } } return sum; } }; // bool dfs(int cur) { // for (int nxt : va[cur]) { // if (!visitb[nxt]) { // visitb[nxt] = true; // clrS.push(nxt); // if (mb[nxt] == 0 || dfs(mb[nxt])) { // ma[cur] = nxt; // mb[nxt] = cur; // return true; // } // } // } // return false; // } // int bipartite_matching() { // memset(ma, -1, sizeof(ma)); // memset(mb, -1, sizeof(mb)); // int ret = 0; // for (int i = 1; i <= cnt; i++) { // while (!clrS.empty()) { // visitb[clrS.top()] = false; // clrS.pop(); // } // if (dfs(i)) ++ret; // } // return ret; // } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> s[i]; } cnt = cnt2 = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i][j] != 'R') continue; if (j + 2 < m) { if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') { ++cnt; a[i][j] = cnt; a[i][j + 1] = cnt; a[i][j + 2] = cnt; } } if (i + 2 < n) { if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') { ++cnt2; // b[i][j]= cnt2; // b[i + 1][j]= cnt2; // b[i + 2][j]= cnt2; } } } } dinic<int> D(cnt + cnt2 + 2, 0, 1); for (int i = 1; i <= cnt; i++) { D.add_edge(0, i + 1, 1); } for (int i = 1; i <= cnt2; i++) { D.add_edge(cnt + i + 1, 1, 1); } int cnt3 = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i][j] != 'R') continue; if (i + 2 < n) { if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') { ++cnt3; if (a[i][j] != 0) { D.add_edge(a[i][j] + 1, cnt + cnt3 + 1, D.INF); } if (a[i + 1][j] != 0) { D.add_edge(a[i + 1][j] + 1, cnt + cnt3 + 1, D.INF); } if (a[i + 2][j] != 0) { D.add_edge(a[i + 2][j] + 1, cnt + cnt3 + 1, D.INF); } // b[i][j]= cnt2; // b[i + 1][j]= cnt2; // b[i + 2][j]= cnt2; } } } } // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // if (a[i][j] != 0 && b[i][j] != 0) { // D.add_edge(a[i][j] + 1, cnt + b[i][j] + 1, D.INF); // // va[a[i][j]].push_back(b[i][j]); // } // } // } cout << cnt + cnt2 - D.max_flow() << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...