結果

問題 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");
    }
    
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0