結果

問題 No.177 制作進行の宮森あおいです！
コンテスト
ユーザー imulan
提出日時 2017-10-18 16:34:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,664 bytes
コンパイル時間 1,892 ms
コンパイル使用メモリ 176,188 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-18 14:34:24
合計ジャッジ時間 2,283 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

// (行き先,容量,逆辺)
struct edge{ int to,cap,rev; };

const int MAX_V = 222; // TODO:initialize
const int F_INF = 191919; // TODO:initialize
vector<edge> G[MAX_V];
int level[MAX_V]; // sからの距離
int iter[MAX_V]; // どこまで調べ終わったか

void add_edge(int from, int to, int cap){
    G[from].pb({to,cap,(int)G[to].size()});
    G[to].pb({from,0,(int)G[from].size()-1});
}

void dinic_bfs(int s){
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(e.cap>0 && level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

// 増加パスをdfsで探す
int dinic_dfs(int v, int t, int f){
    if(v==t) return f;
    for(int &i=iter[v]; i<(int)G[v].size(); ++i){
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            int d = dinic_dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// sからtへの最大流
int max_flow(int s, int t){
    int flow = 0;
    while(1){
        dinic_bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dinic_dfs(s,t,F_INF))>0) flow+=f;
    }
}

int main()
{
    int w,n;
    cin >>w >>n;

    rep(i,n)
    {
        int x;
        cin >>x;
        add_edge(i, n+i, x);
    }

    int m;
    cin >>m;
    rep(i,m)
    {
        int x;
        cin >>x;
        add_edge(2*n+i, 2*n+m+i, x);
    }

    rep(i,m)
    {
        vector<bool> ok(n,true);
        int q;
        cin >>q;
        while(q--)
        {
            int x;
            cin >>x;
            ok[x-1] = false;
        }

        rep(j,n)if(ok[j]) add_edge(n+j, 2*n+i, 11111);
    }

    int S = 2*n+2*m, T = S+1;
    rep(i,n) add_edge(S, i, 11111);
    rep(i,m) add_edge(2*n+m+i, T, 11111);

    cout << (max_flow(S,T)>=w?"SHIROBAKO":"BANSAKUTSUKITA") << endl;
    return 0;
}
0