結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー |
|
提出日時 | 2017-02-07 00:34:10 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,606 bytes |
コンパイル時間 | 1,303 ms |
コンパイル使用メモリ | 101,404 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 08:45:41 |
合計ジャッジ時間 | 2,490 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
コンパイルメッセージ
main.cpp: In instantiation of ‘void Dinic<T>::add_edge(int, int, T) [with T = int]’: main.cpp:145:17: required from here main.cpp:92:58: warning: narrowing conversion of ‘(&((Dinic<int>*)this)->Dinic<int>::graph.std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::operator[](((std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::size_type)to)))->std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size()’ from ‘std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 92 | graph[from].push_back((edge) {to, cap, graph[to].size()}); | ~~~~~~~~~~~~~~^~ main.cpp:93:61: warning: narrowing conversion of ‘((&((Dinic<int>*)this)->Dinic<int>::graph.std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::operator[](((std::vector<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >, std::allocator<std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> > > >::size_type)from)))->std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size() - 1)’ from ‘std::vector<Dinic<int>::edge, std::allocator<Dinic<int>::edge> >::size_type’ {aka ‘long unsigned int’} to ‘int’ [-Wnarrowing] 93 | graph[to].push_back((edge) {from, 0, graph[from].size() - 1}); | ~~~~~~~~~~~~~~~~~~~^~~
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <cctype>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <utility>#include <vector>#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)using namespace std;typedef long long int ll;typedef vector<int> VI;typedef vector<ll> VL;typedef pair<int, int> PI;/*** Dinic's algorithm for maximum flow problem.* Header requirement: vector, queue* Verified by: ABC010-D(http://abc010.contest.atcoder.jp/submissions/602810)* ARC031-D(http://arc031.contest.atcoder.jp/submissions/1050071)* POJ 3155(http://poj.org/problem?id=3155)*/template<class T = int>class Dinic {private:struct edge {int to;T cap;int rev; // rev is the position of reverse edge in graph[to]};std::vector<std::vector<edge> > graph;std::vector<int> level;std::vector<int> iter;/* Perform bfs and calculate distance from s */void bfs(int s) {level.assign(level.size(), -1);std::queue<int> que;level[s] = 0;que.push(s);while (! que.empty()) {int v = que.front(); que.pop();for (int i = 0; i < graph[v].size(); ++i) {edge &e = graph[v][i];if (e.cap > 0 && level[e.to] == -1) {level[e.to] = level[v] + 1;que.push(e.to);}}}}/* search augment path by dfs.if f == -1, f is treated as infinity. */T dfs(int v, int t, T f) {if (v == t) {return f;}for (int &i = iter[v]; i < graph[v].size(); ++i) {edge &e = graph[v][i];if (e.cap > 0 && level[v] < level[e.to]) {T newf = f == -1 ? e.cap : std::min(f, e.cap);T d = dfs(e.to, t, newf);if (d > 0) {e.cap -= d;graph[e.to][e.rev].cap += d;return d;}}}return 0;}public:/* v is the number of vertices (labeled from 0 .. v-1) */Dinic(int v) : graph(v), level(v, -1), iter(v, 0) {}void add_edge(int from, int to, T cap) {graph[from].push_back((edge) {to, cap, graph[to].size()});graph[to].push_back((edge) {from, 0, graph[from].size() - 1});}T max_flow(int s, int t) {T flow = 0;while (1) {bfs(s);if (level[t] < 0) {return flow;}iter.assign(iter.size(), 0);T f;while ((f = dfs(s, t, -1)) > 0) {flow += f;}}}std::pair<T,std::vector<int> > max_flow_cut(int s, int t) {T flow = 0;while (1) {bfs(s);if (level[t] < 0) {std::vector<int> ret;for (int i = 0; i < graph.size(); ++i) {if (level[i] < 0) {ret.push_back(i);}}return std::pair<T, std::vector<int> >(flow, ret);}iter.assign(iter.size(), 0);T f;while ((f = dfs(s, t, -1)) > 0) {flow += f;}}}};int main(void){int w, n;cin >> w >> n;VI j(n);REP(i, 0, n) { cin >> j[i]; }int m;cin >> m;VI c(m);REP(i, 0, m) { cin >> c[i]; }Dinic<int> din(n + m + 2);REP(i, 0, n) {din.add_edge(0, 2 + i, j[i]);}REP(i, 0, m) {din.add_edge(2 + n + i, 1, c[i]);}REP(i, 0, m) {int qi;cin >> qi;VI lim(n, 1e8);REP(j, 0, qi) {int x;cin >> x;x--;lim[x] = 0;}REP(j, 0, n) {din.add_edge(2 + j, 2 + n + i, lim[j]);}}cout << (din.max_flow(0, 1) >= w ? "SHIROBAKO" : "BANSAKUTSUKITA") << endl;}