結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | yosupot |
提出日時 | 2015-04-02 23:27:30 |
言語 | C++11 (gcc 11.4.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | AC | 2 ms
6,940 KB |
ソースコード
#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; }