結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2015-04-02 23:27:30 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,276 bytes |
コンパイル時間 | 833 ms |
コンパイル使用メモリ | 79,460 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-03 23:45:00 |
合計ジャッジ時間 | 1,537 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <iostream>#include <cstring>#include <algorithm>#include <vector>#include <map>#include <queue>#include <set>#include <cassert>#include <cstdio>#include <bitset>using namespace std;typedef long long ll;/*** Dinic法による最大流** ほとんど蟻本そのまま* template引数のint Vは頂点数*/template<int V>struct MaxFlow {using T = int; /// 辺の重みの型const T INF = 1<<28;struct Edge {int to, rev;T cap;};vector<Edge> g[V];int level[V];int iter[V];/// 初期化void init() {for (int i = 0; i < V; i++) {g[i].clear();}}/// 有向辺の追加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 < (int)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;}// sからtへの最大流を返す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;}}}};const int MN = 60;int j[MN];int c[MN];bool g[MN][MN];MaxFlow<MN*3> mf;int main() {int w;cin >> w;int n;cin >> n;for (int i = 0; i < n; i++) {cin >> j[i];}int m;cin >> m;for (int i = 0; i < m; i++) {cin >> c[i];}for (int i = 0; i < m; i++) {int q;cin >> q;for (int j = 0; j < q; j++) {int x;cin >> x; x--;g[x][i] = true;}}int vs = 2*MN-2, vt = 2*MN-1;for (int i = 0; i < n; i++) {mf.add(vs, i, j[i]);}for (int i = 0; i < m; i++) {mf.add(MN+i, vt, c[i]);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (g[i][j]) continue;mf.add(i, MN+j, 100000);}}if (mf.exec(vs, vt) < w) {cout << "BANSAKUTSUKITA" << endl;} else {cout << "SHIROBAKO" << endl;}return 0;}