結果

問題 No.177 制作進行の宮森あおいです！
ユーザー tkzw_21
提出日時 2015-04-03 08:23:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,155 bytes
コンパイル時間 1,527 ms
コンパイル使用メモリ 174,400 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-04 01:36:44
合計ジャッジ時間 2,145 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//Max-Flow,最大流
template<int V>
struct MaxFlow{
    using T = double;
    const T INF = 1<<28;
    
    struct Edge{
        int to,rev;
        T cap;
    };
    vector<Edge> g[V];
    int level[V];
    int iter[V];
     void add(int from, int to, T cap) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap});
        g[to].push_back(Edge{from, (int)g[from].size()-1, 0});
    }
    void add_multi(int from, int to, T cap) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap});
        g[to].push_back(Edge{from, (int)g[from].size()-1, cap});
    }
    void bfs(int s){
        fill_n(level,V,-1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty()){
            int v = que.front();que.pop();
            for(Edge e: g[v]){
                if(e.cap <= 0)continue;
                if(level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    T dfs(int v,int t,T f){
        if(v == t)return f;
        for(int &i = iter[v];i < g[v].size();i++){
            Edge &e = g[v][i];
            if(e.cap <= 0)continue;
            if(level[v] < level[e.to]){
                T d = dfs(e.to,t,min(f,e.cap));
                if(d <= 0)continue;
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }
    T exec(int s,int t){
        T flow = 0;
        while(true){
            bfs(s);
            if(level[t] < 0)return flow;
            fill_n(iter,V,0);
            T f;
            while((f = dfs(s,t,INF)) > 0){
                flow += f;
            }
        }
    }
};
int main(void) {
    int w,n;
    cin >> w >> n;
    vector<int> j(n);
    for(int i=0;i<n;i++)cin >> j[i];
    int m;
    cin >> m;
    vector<int> c(m);
    for(int i=0;i<m;i++)cin >> c[i];
    vector<vector<bool>> link(n,vector<bool>(m,true));
    for(int i=0;i<m;i++){
        int q;cin >> q;
        for(int j=0;j<q;j++){
            int x;cin >> x;x--;
            link[x][i] = false;
        }
    }
    MaxFlow<120> mf;
    for(int i=0;i<n;i++)mf.add(n+m,i,j[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(link[i][j])mf.add(i,j+n,1<<28);
        }
    }
    for(int i=0;i<m;i++)mf.add(i+n,n+m+1,c[i]);
    cout << (mf.exec(m+n,m+n+1)>=w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0