#115867 (C++11) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	pekempey
提出日時	2016-09-09 22:38:26
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	2,237 bytes
コンパイル時間	1,611 ms
コンパイル使用メモリ	174,648 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-24 14:44:39
合計ジャッジ時間	3,177 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	3 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	2 ms 4,348 KB
testcase_04	AC	2 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	2 ms 4,348 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,348 KB
testcase_10	AC	2 ms 4,348 KB
testcase_11	AC	2 ms 4,348 KB
testcase_12	AC	2 ms 4,348 KB
testcase_13	AC	2 ms 4,348 KB
testcase_14	AC	1 ms 4,348 KB
testcase_15	AC	1 ms 4,348 KB
testcase_16	AC	4 ms 4,348 KB
testcase_17	AC	4 ms 4,348 KB
testcase_18	AC	4 ms 4,348 KB
testcase_19	AC	2 ms 4,348 KB
testcase_20	AC	3 ms 4,348 KB
testcase_21	AC	4 ms 4,348 KB
testcase_22	AC	3 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	2 ms 4,348 KB
testcase_25	AC	1 ms 4,348 KB
testcase_26	AC	1 ms 4,348 KB
testcase_27	AC	1 ms 4,348 KB
testcase_28	AC	3 ms 4,348 KB
testcase_29	AC	3 ms 4,348 KB
testcase_30	AC	3 ms 4,348 KB
testcase_31	AC	4 ms 4,348 KB
testcase_32	AC	3 ms 4,348 KB
testcase_33	AC	3 ms 4,348 KB
testcase_34	AC	2 ms 4,348 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	2 ms 4,348 KB
testcase_37	AC	4 ms 4,348 KB
testcase_38	AC	5 ms 4,348 KB
testcase_39	AC	3 ms 4,348 KB
testcase_40	AC	3 ms 4,348 KB
testcase_41	AC	2 ms 4,348 KB
testcase_42	AC	2 ms 4,348 KB
testcase_43	AC	2 ms 4,348 KB
testcase_44	AC	4 ms 4,348 KB
testcase_45	AC	2 ms 4,348 KB
testcase_46	AC	1 ms 4,348 KB
testcase_47	AC	2 ms 4,348 KB
testcase_48	AC	4 ms 4,348 KB
testcase_49	AC	2 ms 4,348 KB
testcase_50	AC	2 ms 4,348 KB
testcase_51	AC	4 ms 4,348 KB
testcase_52	AC	2 ms 4,348 KB
testcase_53	AC	2 ms 4,348 KB
testcase_54	AC	2 ms 4,348 KB
testcase_55	AC	2 ms 4,348 KB
testcase_56	AC	2 ms 4,348 KB
testcase_57	AC	2 ms 4,348 KB
testcase_58	AC	3 ms 4,348 KB
testcase_59	AC	2 ms 4,348 KB
testcase_60	AC	5 ms 4,348 KB
testcase_61	AC	5 ms 4,348 KB
testcase_62	AC	2 ms 4,348 KB
testcase_63	AC	2 ms 4,348 KB
testcase_64	AC	2 ms 4,348 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード