結果

問題 No.177 制作進行の宮森あおいです！
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-02 23:37:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,056 bytes
コンパイル時間 1,264 ms
コンパイル使用メモリ 168,416 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 01:27:45
合計ジャッジ時間 1,848 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int, int)’:
main.cpp:18:32: warning: narrowing conversion of ‘g[t].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   18 |         Edge a = { t, g[t].size(), 0, cap };
      |                       ~~~~~~~~~^~
main.cpp:19:32: warning: narrowing conversion of ‘g[s].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing]
   19 |         Edge b = { s, g[s].size(), 0, cap };
      |                       ~~~~~~~~~^~

ソースコード

diff # 

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

const int maxnodes = 5000;

int nodes = maxnodes, src, dest;
int dist[maxnodes], q[maxnodes], work[maxnodes];

struct Edge {
	int to, rev;
	int f, cap;
};

vector<Edge> g[maxnodes];

// Adds bidirectional edge
void addEdge(int s, int t, int cap){
	Edge a = { t, g[t].size(), 0, cap };
	Edge b = { s, g[s].size(), 0, cap };
	g[s].push_back(a);
	g[t].push_back(b);
}

bool dinic_bfs() {
	fill(dist, dist + nodes, -1);
	dist[src] = 0;
	int qt = 0;
	q[qt++] = src;
	for (int qh = 0; qh < qt; qh++) {
		int u = q[qh];
		for (int j = 0; j < (int)g[u].size(); j++) {
			Edge &e = g[u][j];
			int v = e.to;
			if (dist[v] < 0 && e.f < e.cap) {
				dist[v] = dist[u] + 1;
				q[qt++] = v;
			}
		}
	}
	return dist[dest] >= 0;
}

int dinic_dfs(int u, int f) {
	if (u == dest)
		return f;
	for (int &i = work[u]; i < (int)g[u].size(); i++) {
		Edge &e = g[u][i];
		if (e.cap <= e.f) continue;
		int v = e.to;
		if (dist[v] == dist[u] + 1) {
			int df = dinic_dfs(v, min(f, e.cap - e.f));
			if (df > 0) {
				e.f += df;
				g[v][e.rev].f -= df;
				return df;
			}
		}
	}
	return 0;
}


int maxFlow(int _src, int _dest) {
	src = _src;
	dest = _dest;
	int result = 0;
	while (dinic_bfs()) {
		fill(work, work + nodes, 0);
		while (int delta = dinic_dfs(src, INT_MAX))
			result += delta;
	}
	return result;
}


int main() {
	int W;
	cin >> W;
	int N , M;
	cin >> N;
	vector<int> v(N);
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}
	cin >> M;

	nodes = N + M + 2;
	for (int i = 0; i < N; i++)
	{
		addEdge(N + M, i, v[i]);
	}

	for (int i = 0; i < M; i++)
	{
		int C;
		cin >> C;
		addEdge(N + i, N + M + 1, C);
	}

	for (int i = 0; i < M; i++)
	{
		int Q;
		cin >> Q;
		set<int> s;
		for (int j = 0; j < Q; j++)
		{
			int temp;
			cin >> temp;
			temp--;
			s.insert(temp);
		}
		for (int j = 0; j < N; j++)
		{
			if (s.find(j) != s.end()) continue;
			addEdge(j, N + i, 9999999);
		}
	}

	int flow = maxFlow(N + M, N + M + 1);
	if (flow >= W) cout << "SHIROBAKO" << endl;
	else cout << "BANSAKUTSUKITA" << endl;
}
0