結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー nablaenergy_21
提出日時 2015-04-15 01:16:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,780 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 25,216 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 14:31:40
合計ジャッジ時間 745 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:53:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |         scanf("%d %d",&W,&N);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:55:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |                 scanf("%d",&J[i]);
      |                 ~~~~~^~~~~~~~~~~~
main.cpp:57:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   57 |         scanf("%d",&M);
      |         ~~~~~^~~~~~~~~
main.cpp:59:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |                 scanf("%d",&C0[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp:62:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |                 scanf("%d",&Q[i]);
      |                 ~~~~~^~~~~~~~~~~~
main.cpp:64:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |                         scanf("%d",&X[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~

ソースコード

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