結果

問題 No.177 制作進行の宮森あおいです！
ユーザー kazumakazuma
提出日時 2017-06-25 18:54:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,115 bytes
コンパイル時間 2,396 ms
コンパイル使用メモリ 182,492 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 09:00:20
合計ジャッジ時間 3,292 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 3 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;

class MaxFlow {
	struct edge {
		int to, cap, rev;
		edge(int to_, int cap_, int rev_) : to(to_), cap(cap_), rev(rev_) {};
	};

	int V;
	vector<vector<edge>> G;
	vector<int> level;
	vector<int> iter;

	void BFS(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (size_t i = 0; i < 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;
	}

public:
	MaxFlow(int _V) : V(_V), G(_V), level(_V), iter(_V) {}
	void add(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));
	}
	int Dinic(int s, int t) {
		int flow = 0;
		while (true) {
			BFS(s);
			if (level[t] < 0) return flow;
			fill(iter.begin(), iter.end(), 0);
			int f;
			while ((f = DFS(s, t, INF)) > 0) {
				flow += f;
			}
		}
	}
};

int main()
{
	int W, N, M;
	cin >> W >> N;
	vector<int> J(N);
	for (int i = 0; i < N; i++) {
		cin >> J[i];
	}
	cin >> M;
	vector<int> C(M);
	for (int i = 0; i < M; i++) {
		cin >> C[i];
	}
	vector<vector<int>> G(M, vector<int>(N, 1));
	for (int i = 0, Q; i < M; i++) {
		cin >> Q;
		for (int j = 0, X; j < Q; j++) {
			cin >> X; X--;
			G[i][X] = 0;
		}
	}
	MaxFlow mf(N + M + 2);
	for (int i = 0; i < N; i++) {
		mf.add(N + M, i, J[i]);
	}
	for (int i = 0; i < M; i++) {
		mf.add(N + i, N + M + 1, C[i]);
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (G[i][j]) {
				mf.add(j, N + i, INF);
			}
		}
	}
	cout << (mf.Dinic(N + M, N + M + 1) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
	return 0;
}
0