結果

問題 No.177 制作進行の宮森あおいです！
ユーザー EmKjpEmKjp
提出日時 2015-04-03 00:05:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,587 bytes
コンパイル時間 828 ms
コンパイル使用メモリ 94,376 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-17 03:47:26
合計ジャッジ時間 1,439 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
typedef vector<int> VI;
typedef vector<VI> VVI;

typedef int weight;
weight INF = 1<<28;

const int MAXV = 200;//102;
class Dinic
{
    int n; 
    weight capacity[MAXV][MAXV] , flow[MAXV][MAXV];
    int level[MAXV] ;
    bool used[MAXV];
    vector<vector<int> > adj;
public : 
    Dinic(int n) : n(n) , adj(n) {
        memset(capacity , 0 , sizeof(capacity));
    }
    void add_edge(int from , int to , weight flow)
    {
        if(capacity[from][to]==0 && flow){
            adj[from].push_back(to);
            adj[to].push_back(from);
        }
        capacity[from][to] += flow;
    }
    weight get_flow(int from , int to){
        return flow[from][to]-flow[to][from];
    }
    weight residue(int from,int to) {
        return capacity[from][to]-get_flow(from,to) ;
    }
    weight augment(int pos, int end , weight cur) {
        weight flow_out = 0 ;
        vector<int>::const_iterator it = adj[pos].begin() , it_end = adj[pos].end(); 
        for(; it != it_end ; it++){
            int i = *it; 
            if (level[i]==level[pos]+1) {
                weight f = min(cur - flow_out , residue(pos,i)) ;         
                if(f<=0) continue;
                if (i==end ||(!used[i] && (f = augment(i , end , f)) > 0)) {
                    flow[pos][i] += f;
                    flow_out += f ; 
                    if(cur-flow_out==0) return flow_out ; 
                }
            }
        }
        used[pos] = flow_out == 0;
        return flow_out;
    }
    bool levelize(int s ,int t){
        memset(level , -1 , sizeof(level));
        queue<int> q;
        level[s] = 0; q.push(s);
        while(!q.empty()) {
            int pos = q.front(); q.pop();
            vector<int>::const_iterator 
                it = adj[pos].begin() , it_end = adj[pos].end(); 
            for(; it != it_end ; it++){
                int dest = *it;
                if (level[dest] == -1 && residue(pos, dest) > 0) {
                    level[dest] = level[pos] + 1;
                    q.push(dest);
                }
            }
        }
        return (level[t]!=-1) ;
    }
    weight run(int s, int t)
    {
        memset(flow , 0 , sizeof(flow));
        weight flow_sum=0;
        while(levelize(s,t)) {
            fill_n(used , n , false);
            flow_sum += augment(s, t , INF);
        }
        return flow_sum;
    }
};

int main()
{
    int W;
    int N;
    cin>>W>>N;
    VI J(N);
    FOR(i,N) cin>>J[i];
    int M;
    cin>>M;
    VI C(M);
    FOR(i,M) cin>>C[i];
    int source = N + M;
    int sink = source + 1;
    Dinic D(sink + 1);
    FOR(i,M){
        int q;
        cin>>q;
        VI fit(N, 1);
        FOR(_,q){
            int x;
            scanf("%d",&x);
            x--;
            fit[x] = 0;
        }
        FOR(j, N){
            if(fit[j]) D.add_edge(j, N + i, 1<<28);
        }
    }
    FOR(i,N) D.add_edge(source, i, J[i]);
    FOR(i,M) D.add_edge(N+i, sink, C[i]);
    puts(D.run(source,sink) >= W ? "SHIROBAKO" : "BANSAKUTSUKITA");
    return 0;
}
0