//一人が複数の人と結びつくことはできる!でも相性の悪い人とはだめ… //作画同士や原画同士はやり取りなし。 //1方向に作業がすすむ。ってことは、最大フローがW以上になるかどうかだよね、グラフは2部マッチングみたいに作る。 //ただし流量を1ではなくて、JiとかXiとかにする。(フロー初めて) //しかし、フローってNP-Hardじゃないんだよなー(ググった、不思議だ //…フローなのは一瞬で分かったけど、フローってどうやるんだ!?(フローに対する考察不足, 初実装) #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int w; int n; int J[50]; int m; int C[50]; int ok[50][50]; //ok[J][C] int Q, X; int flow[114][114] = {0}; //増加道を探す、ある:1,ない:0を返す、一応prevを更新するので、これを使って適当に経路復元してくれ bool get_incway(int s, int t, int *prev) { queue que; bool gone[114] = {false}; que.push(s); while(!que.empty() ) { int v = que.front(); que.pop(); if ( gone[v] ) continue; //cout << v << endl; gone[v] = true; for(int i = 0; i <= n+m+1; i++ ) { if ( flow[v][i] >= 1 && prev[v] != i ) { prev[i] = v; que.push(i); } } } return gone[t]; } int Maxflow(int s, int t) { int prev[114]; //prev[i] = iの前に行ったノード int ans = 0; while( get_incway(s, t, prev) ) { //フロー量のカウント ans++; //残余ネットワークを作るとかフロー流すとか int no = t; //cout << endl; while( prev[no] != s ) { //cout << "no = " << no << endl; flow[ prev[no] ][no]--; //フロー流す flow[no][ prev[no] ]++; //残余ネットワーク増やす no = prev[no]; } //無限ループしてなければこれによってWAになる if ( ans >= 1000 ) break; } return ans; } //node[0]…始点、node[n+m+1]…終点、有向グラフ(が基本) (逆辺は残余ネットワークとして用いる) signed main() { int i, j; cin >> w; cin >> n; for( i = 0; i < n; i++ ) { cin >> J[i]; flow[0][i+1] = J[i]; } cin >> m; for( i = 0; i < m; i++ ) { cin >> C[i]; } for( i = 0; i < m; i++ ) { cin >> Q; for( j = 0; j < n; j++ ) { ok[j][i] = 1; } for( j = 0; j < Q; j++ ) { cin >> X; X--; ok[X][i] = 0; } } for( i = 0; i < n; i++ ) { for( j = 0; j < m; j++ ) { if ( ok[i][j] ) { //cout << i << " " << j << endl; flow[i+1][n+1+j] = J[i]; } } } for( i = 0; i < m; i++ ) { flow[n+1+i][n+m+1] = C[i]; } /*for( i = 0; i < n+m+2; i++ ) { for( j = 0; j < n+m+2; j++ ) { cout << flow[i][j] << " " ; } cout << endl; }*/ //最大フローを求める int maxf = Maxflow(0, n+m+1); if ( maxf >= w ) cout << "SHIROBAKO" << endl; else cout << "BANSAKUTSUKITA" << endl; return 0; }