結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | nablaenergy_21 |
提出日時 | 2015-04-15 01:16:54 |
言語 | C++11 (gcc 11.4.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 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 | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
コンパイルメッセージ
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]); | ~~~~~^~~~~~~~~~~~~~~
ソースコード
#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"); } }