結果

問題 No.177 制作進行の宮森あおいです！
ユーザー threepipes_s
提出日時 2015-05-19 03:21:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,597 bytes
コンパイル時間 747 ms
コンパイル使用メモリ 65,776 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-06 05:40:34
合計ジャッジ時間 2,523 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 1 RE * 7
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
using namespace std;
int w, n, m;
int J[50];
int C[50];
struct Node{
    int id;
    vector<int> edge;
};
int cap[50][50];
Node node[102];
bitset<50> bs;
bitset<102> used;
int dfs(int, int);
void add(int, int, int);
int main(){
    cin >> w >> n;
    for (int i = 0; i<n; i++) cin >> J[i];
    cin >> m;
    for (int i = 0; i<m; i++) cin >> C[i];
    int nodes = 2 + n + m;
    for (int i = 0; i<nodes; i++) node[i].id = i;
    for (int i = 0; i<n; i++){
        // nodeの0から1+iにJ[i]の辺を張る
        add(0, 1 + i, J[i]);
    }
    for (int i = 0; i<m; i++){
        int q;
        cin >> q;
        bs.reset();
        for (int j = 0; j<q; j++){
            int x;
            cin >> x;
            bs.set(x-1);
        }
        for (int j = 0; j<n; j++){
            if(!bs.test(j)){
                // nodeの1+jから1+n+iにJ[j]の辺を張る
                add(1 + j, 1 + n + i, J[j]);
            }
        }
        // nodeの1+n+iから1+n+mにC[i]の辺を張る
        add(1 + n + i, 1 + n + m, C[i]);
    }
    int res = 0;
    while (true){
        used.reset();
        int flow = dfs(0, 1000000);
        if (flow == 0) break;
        res += flow;
    }
    cout << ((res < w) ? "BANSAKUTSUKITA": "SHIROBAKO") << endl;
}
int dfs(int from, int flow){
    if (from == n + m + 1) return flow;
    if (used.test(from)) return 0;
    used.set(from);
    for (auto i = node[from].edge.begin(); i != node[from].edge.end(); i++){
        int to = *i;
        if (!cap[from][to]) continue;
        int f = dfs(to, min(flow, cap[from][to]));
        if (f == 0) continue;
        cap[from][to] -= f;
        cap[to][from] += f;
        return f;
    }
    return 0;
}
void add(int from, int to, int flow){
    node[from].edge.push_back(to);
    cap[from][to] = flow;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0