結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー pekempey
提出日時 2016-09-09 22:38:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 2,237 bytes
コンパイル時間 1,789 ms
コンパイル使用メモリ 174,216 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:04:15
合計ジャッジ時間 3,367 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

class MaxFlow {
public:
	MaxFlow(int n) : g(n), dist(n), ptr(n) {}

	void add(int u, int v, long long c) {
		int i = g[u].size();
		int j = g[v].size();
		g[u].push_back({ v, j, c });
		g[v].push_back({ u, i, 0 });
	}

	long long operator()(int s, int t) {
		long long result = 0;
		while (bfs(s, t)) {
			long long f;
			do {
				f = dfs(s, t, 1e18);
				result += f;
			} while (f > 0);
		}
		return result;
	}

private:
	struct edge {
		int next;
		int rev;
		long long cap;
	};

	vector<vector<edge>> g;
	vector<int> dist;
	vector<int> ptr;

	bool bfs(int s, int t) {
		fill(ptr.begin(), ptr.end(), 0);
		fill(dist.begin(), dist.end(), -1);
		dist[s] = 0;

		queue<int> q;
		q.push(s);

		while (!q.empty()) {
			int curr = q.front();
			q.pop();

			for (edge e : g[curr]) {
				if (e.cap > 0 && dist[e.next] == -1) {
					dist[e.next] = dist[curr] + 1;
					q.push(e.next);
				}
			}
		}
		return dist[t] >= 0;
	}

	long long dfs(int curr, int sink, long long f) {
		if (curr == sink) return f;
		while (ptr[curr] < g[curr].size()) {
			edge &e = g[curr][ptr[curr]++];
			if (e.cap > 0 && dist[curr] < dist[e.next]) {
				long long d = dfs(e.next, sink, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					g[e.next][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
};

int main() {
	int h, w;
	cin >> h >> w;

	vector<string> g(h);
	for (int i = 0; i < h; i++) {
		cin >> g[i];
	}

	MaxFlow mf(h * w + 2);
	int src = h * w;
	int sink = src + 1;

	long long white = 0;
	long long black = 0;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (g[i][j] == 'w') {
				mf.add(i * w + j, sink, 1);
				white++;
			}
			if (g[i][j] != 'b') continue;
			black++;
			mf.add(src, i * w + j, 1);
			int dy[] = { 0, 1, 0, -1 };
			int dx[] = { 1, 0, -1, 0 };

			for (int k = 0; k < 4; k++) {
				int ny = i + dy[k];
				int nx = j + dx[k];

				if (ny >= h || ny < 0 || nx >= w || nx < 0) continue;

				if (g[ny][nx] == 'w') {
					mf.add(i * w + j, ny * w + nx, 1);
				}
			}
		}
	}

	long long f = mf(src, sink);
	black -= f;
	white -= f;

	long long ans = f * 100 + min(black, white) * 10 + max(black, white) - min(black, white);

	cout << ans << endl;
}
0