結果
問題 | No.421 しろくろチョコレート |
ユーザー |
|
提出日時 | 2022-02-15 11:32:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 2,985 bytes |
コンパイル時間 | 2,490 ms |
コンパイル使用メモリ | 204,872 KB |
最終ジャッジ日時 | 2025-01-27 23:15:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
#line 1 "main.cpp"#include <bits/stdc++.h>#line 6 "/mnt/c/Users/araar/documents/kyopro/library/graph/FordFulkerson.cpp"template <typename T>class FordFulkerson {public:struct edge {int to;T cap;int rev;};int n;std::vector<std::vector<edge>> g;std::vector<bool> used;FordFulkerson(int n = 0): n(n), g(n), used(n) {}void add_edge(int from, int to, T cap) {assert(0 <= from && from < n);assert(0 <= to && to < n);assert(0 <= cap);g[from].push_back((edge){to, cap, int(g[to].size())});g[to].push_back((edge){from, 0LL, int(g[from].size() - 1)});}T dfs(int v, int goal_v, T flow) {if(v == goal_v) return flow;used[v] = true;for(int i = 0; i < (int)g[v].size(); i++) {edge &e = g[v][i];if(!used[e.to] && e.cap > 0) {T next_flow = dfs(e.to, goal_v, std::min(flow, e.cap));if(next_flow > 0) {e.cap -= next_flow;g[e.to][e.rev].cap += next_flow;return next_flow;}}}return 0;}T max_flow(int s, int t, T ma = std::numeric_limits<T>::max()) {assert(0 <= s && s < n);assert(0 <= t && t < n);T flow = 0;while(1) {used = std::vector<bool>(n, false);T f = dfs(s, t, ma);if(f == 0) return flow;flow += f;}}};#line 3 "main.cpp"using namespace std;#define rep(i, n) for(int i = 0; i < int(n); i++)using ll = long long;using P = pair<int, int>;int main() {int h, w;cin >> h >> w;vector<string> s(h);rep(i, h) cin >> s[i];FordFulkerson<int> mcf_graph(h * w + 2);int st = h * w, go = h * w + 1;rep(i, h) {rep(j, w) {// cout << i * w + j << " ";if(s[i][j] == '.')continue;else if(s[i][j] == 'w') {mcf_graph.add_edge(st, i * w + j, 1);if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * w + j, i * w + j + 1, 1);if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge(i * w + j, (i + 1) * w + j, 1);}else {mcf_graph.add_edge(i * w + j, go, 1);if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * w + j + 1, i * w + j, 1);if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge((i + 1) * w + j, i * w + j, 1);}}// cout << endl;}int flowcnt = mcf_graph.max_flow(st, go);int bcnt = 0, wcnt = 0;rep(i, h) rep(j, w) {if (s[i][j] == 'w') wcnt++;else if (s[i][j] == 'b')bcnt++;}cout << 100 * flowcnt + (min(bcnt, wcnt) - flowcnt) * 10 + max(bcnt, wcnt) - min(bcnt, wcnt) << endl;// cout << flowcnt << endl;return 0;}