結果

問題 No.177 制作進行の宮森あおいです！
ユーザー nablaenergy_21nablaenergy_21
提出日時 2015-04-15 01:16:54
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,780 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 27,968 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-17 20:20:06
合計ジャッジ時間 1,488 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>

#define INF 1000000000

int n,g,C[102][102],F,f,m;
int q[200],fr[102],qf,ql;

void q_a(int a){
	q[ql] = a;
	ql++;
}

int q_t(void){
	qf++;
	return q[qf-1];
}

int min(int a,int b){
	if(a>b){return b;}else{return a;}
}

int bfs(void){
	int i,v,br;
	int rt = -1;
	qf = 0; ql = 0;
	q_a(0);
	for(i=0;i<n;i++){
		fr[i] = -1;
	}
	fr[0] = -2;
	br = 0;
	while(qf<ql){
		v = q_t();
		for(i=0;i<n;i++){
			if(C[v][i]>0 && fr[i]==-1){
				q_a(i);
				fr[i] = v;
				if(i==g){
					br = 1;
					rt = 1;
				}
			}
		}
		if(br == 1){break;}
	}
	return rt;
}

int main(void){
	int v,i,j,k;
	int W,N,J[50],M,C0[50],Q[50],X[50][50];

	scanf("%d %d",&W,&N);
	for(i=0;i<N;i++){
		scanf("%d",&J[i]);
	}
	scanf("%d",&M);
	for(i=0;i<M;i++){
		scanf("%d",&C0[i]);
	}
	for(i=0;i<M;i++){
		scanf("%d",&Q[i]);
		for(j=0;j<Q[i];j++){
			scanf("%d",&X[i][j]);
		}
	}

	n = N+M+2;

	/*
	0が始点。
	1,2,...,Nが原画、N+1,N+2,...,N+Mが作監、N+M+1が終点。
	始点とそれぞれの原画をJ[i]で結ぶ。
	合わない指定されていない原画と作監を、すべてINFで結ぶ。
	それぞれの作監と終点をC0[i]で結ぶ。
	*/
	for(i=0;i<N+M+2;i++){
		for(j=0;j<N+M+2;j++){
			C[i][j] = 0;
		}
	}

	for(i=0;i<N;i++){
		C[0][i+1] = J[i]; 
	}

	for(i=0;i<N;i++){
		for(j=0;j<M;j++){
			C[i+1][j+N+1] = INF;
			for(k=0;k<Q[j];k++){
				if(X[j][k] == i+1){
					C[i+1][j+N+1] = 0;
				}
			}
		}
	}

	for(i=0;i<M;i++){
		C[i+N+1][N+M+1] = C0[i];
	}

	g = N+M+1;

	F = 0;
	while(bfs()>0){
		v = g;
		m = INF;
		while(v != 0){
			m = min(C[fr[v]][v],m);
			v = fr[v];
		}
		f = m;
		F += f;
		v = g;
		while(v != 0){
			C[fr[v]][v] -= f;
			C[v][fr[v]] += f;
			v = fr[v];
		}
		

	}
	if(F<W){
		printf("BANSAKUTSUKITA\n");
	}else{
		printf("SHIROBAKO\n");
	}
	
}
0