이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
// RGW
int n, m;
string s[3005];
int a[3005][3005], b[3005][3005];
vector<int> va[3000005];
int ma[3000005], mb[3000005];
bool visitb[3000005];
int cnt, cnt2;
stack<int> clrS;
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);
}
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |