結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
![]() |
提出日時 | 2015-04-02 23:36:43 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,043 bytes |
コンパイル時間 | 1,560 ms |
コンパイル使用メモリ | 168,280 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-04 01:27:36 |
合計ジャッジ時間 | 1,991 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 11 WA * 2 |
コンパイルメッセージ
main.cpp: In function ‘void addEdge(int, int, int)’: main.cpp:18:32: warning: narrowing conversion of ‘g[t].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 18 | Edge a = { t, g[t].size(), 0, cap }; | ~~~~~~~~~^~ main.cpp:19:32: warning: narrowing conversion of ‘g[s].std::vector<Edge>::size()’ from ‘std::vector<Edge>::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 19 | Edge b = { s, g[s].size(), 0, cap }; | ~~~~~~~~~^~
ソースコード
#include "bits/stdc++.h"using namespace std;const int maxnodes = 5000;int nodes = maxnodes, src, dest;int dist[maxnodes], q[maxnodes], work[maxnodes];struct Edge {int to, rev;int f, cap;};vector<Edge> g[maxnodes];// Adds bidirectional edgevoid addEdge(int s, int t, int cap){Edge a = { t, g[t].size(), 0, cap };Edge b = { s, g[s].size(), 0, cap };g[s].push_back(a);g[t].push_back(b);}bool dinic_bfs() {fill(dist, dist + nodes, -1);dist[src] = 0;int qt = 0;q[qt++] = src;for (int qh = 0; qh < qt; qh++) {int u = q[qh];for (int j = 0; j < (int)g[u].size(); j++) {Edge &e = g[u][j];int v = e.to;if (dist[v] < 0 && e.f < e.cap) {dist[v] = dist[u] + 1;q[qt++] = v;}}}return dist[dest] >= 0;}int dinic_dfs(int u, int f) {if (u == dest)return f;for (int &i = work[u]; i < (int)g[u].size(); i++) {Edge &e = g[u][i];if (e.cap <= e.f) continue;int v = e.to;if (dist[v] == dist[u] + 1) {int df = dinic_dfs(v, min(f, e.cap - e.f));if (df > 0) {e.f += df;g[v][e.rev].f -= df;return df;}}}return 0;}int maxFlow(int _src, int _dest) {src = _src;dest = _dest;int result = 0;while (dinic_bfs()) {fill(work, work + nodes, 0);while (int delta = dinic_dfs(src, INT_MAX))result += delta;}return result;}int main() {int W;cin >> W;int N , M;cin >> N;vector<int> v(N);for (int i = 0; i < N; i++){cin >> v[i];}cin >> M;nodes = N + M + 2;for (int i = 0; i < N; i++){addEdge(N + M, i, v[i]);}for (int i = 0; i < M; i++){int C;cin >> C;addEdge(N + i, N + M + 1, C);}for (int i = 0; i < M; i++){int Q;cin >> Q;set<int> s;for (int j = 0; j < Q; j++){int temp;cin >> temp;s.insert(temp);}for (int j = 0; j < N; j++){if (s.find(j)==s.end()) continue;addEdge(j, N + i, 9999999);}}int flow = maxFlow(N + M, N + M + 1);if (flow >= W) cout << "SHIROBAKO" << endl;else cout << "BANSAKUTSUKITA" << endl;}