結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2022-03-15 04:11:59 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,897 bytes |
コンパイル時間 | 2,801 ms |
コンパイル使用メモリ | 144,616 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-21 16:56:24 |
合計ジャッジ時間 | 5,255 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 WA * 29 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <queue>#include <set>#include <string.h>#include <vector>using namespace std;typedef long long ll;const int INF = INT_MAX;struct Edge {int to;int cap;int rev;Edge(int to = -1, int cap = -1, int rev = -1) {this->to = to;this->cap = cap;this->rev = rev;}};const int MAX_N = 100;const int MAX_V = MAX_N * MAX_N + 10;int level[MAX_V];int iter[MAX_V];vector <Edge> G[MAX_V];void add_edge(int from, int to, int cap) {G[from].push_back(Edge(to, cap, G[to].size()));G[to].push_back(Edge(from, 0, G[from].size() - 1));}void bfs(int s) {memset(level, -1, sizeof(level));queue<int> que;level[s] = 0;que.push(s);while (!que.empty()) {int v = que.front();que.pop();for (int i = 0; i < (int) G[v].size(); ++i) {Edge *e = &G[v][i];if (e->cap > 0 && level[e->to] < 0) {level[e->to] = level[v] + 1;que.push(e->to);}}}}int dfs(int v, int t, int f) {if (v == t) return f;for (int &i = iter[v]; i < (int) G[v].size(); ++i) {Edge *e = &G[v][i];if (e->cap > 0 && level[v] < level[e->to]) {int d = dfs(e->to, t, min(f, e->cap));if (d > 0) {e->cap -= d;G[e->to][e->rev].cap += d;return d;}}}return 0;}int max_flow(int s, int t) {int flow = 0;for (;;) {bfs(s);if (level[t] < 0) return flow;memset(iter, 0, sizeof(iter));int f;while ((f = dfs(s, t, INF)) > 0) {flow += f;}}}int DY[4] = {-1, 0, 1, 0};int DX[4] = {0, 1, 0, -1};int main() {int N, M;cin >> N >> M;string grid[N];int counter[2] = {0, 0};for (int i = 0; i < N; ++i) {cin >> grid[i];for (int j = 0; j < M; ++j) {if (grid[i][j] == 'b') {counter[0]++;} else if (grid[i][j] == 'w') {counter[1]++;}}}int s = MAX_V - 2;int t = MAX_V - 1;for (int y = 0; y < N; ++y) {for (int x = 0; x < M; ++x) {int u = y * M + x;char ch = grid[y][x];if (ch == '.') continue;if (ch == 'b') {add_edge(s, u, 1);} else {add_edge(u, t, 1);}for (int i = 0; i < 4; ++i) {int ny = y + DY[i];int nx = x + DX[i];if (ny < 0 || nx < 0 || N <= ny || M <= nx) continue;if (grid[ny][nx] == '.') continue;if (ch == grid[ny][nx]) continue;int v = ny * M + nx;add_edge(u, v, 1);}}}int mc = max_flow(s, t);int ans = 100 * mc;counter[0] -= mc;counter[1] -= mc;int pc = min(counter[0], counter[1]);ans += 10 * pc;counter[0] -= pc;counter[1] -= pc;ans += counter[0] + counter[1];cout << ans << endl;return 0;}