結果
| 問題 | No.177 制作進行の宮森あおいです！ |
| ユーザー |
 zeke
|
| 提出日時 | 2019-11-12 20:48:02 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 3,873 bytes |
| コンパイル時間 | 888 ms |
| コンパイル使用メモリ | 94,840 KB |
| 最終ジャッジ日時 | 2024-11-14 21:50:15 |
| 合計ジャッジ時間 | 1,294 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In constructor 'FordFulkerson<flow_t>::FordFulkerson(int)':
main.cpp:61:30: error: 'numeric_limits' was not declared in this scope
61 | FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) {
| ^~~~~~~~~~~~~~
main.cpp:61:53: error: expected primary-expression before '>' token
61 | FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) {
| ^
main.cpp:61:59: error: no matching function for call to 'max()'
61 | FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) {
| ~~~~~^~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/string:50,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/locale_classes.h:40,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/ios_base.h:41,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ios:42,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/ostream:38,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/iostream:39,
from main.cpp:7:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
main.cpp:61:59: note: candidate expects 2 arguments, 0 provided
61 | FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) {
| ~~~~~^~
/home/linuxbrew/.linuxbrew/Cellar/gcc
ソースコード
/*
Author:zeke
pass System Test!
GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <math.h>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rep3(var, min, max) for (ll (var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll (var) = (max) - 1; (var) + 1 > (min); --(var))
#define Mp(a,b) make_pair((a),(b))
#define F first
#define S second
#define CIN(s) int (s);cin>>(s);
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll MOD = 1e9 + 7;
ll INF =1e18;
//ここから
template< typename flow_t >
struct FordFulkerson {
struct edge {
int to;
flow_t cap;
int rev;
bool isrev;
int idx;
};
vector< vector< edge > > graph;
vector< int > used;
const flow_t INF;
int timestamp;
FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) {
graph.resize(n);
used.assign(n, -1);
}
void add_edge(int from, int to, flow_t cap, int idx = -1) {
graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx});
graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx});
}
flow_t dfs(int idx, const int t, flow_t flow) {
if(idx == t) return flow;
used[idx] = timestamp;
for(auto &e : graph[idx]) {
if(e.cap > 0 && used[e.to] != timestamp) {
flow_t d = dfs(e.to, t, min(flow, e.cap));
if(d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
flow_t max_flow(int s, int t) {
flow_t flow = 0;
for(flow_t f; (f = dfs(s, t, INF)) > 0; timestamp++) {
flow += f;
}
return flow;
}
void output() {
for(int i = 0; i < graph.size(); i++) {
for(auto &e : graph[i]) {
if(e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
}
}
}
};
/*使い方:
FordFulkerson(V):= 頂点数 Vで初期化する。
add_edge(from,to,cap):=頂点fromからtoに容量capの辺を張る。
max_flow(s,t,f):= 頂点sからtに最大流を流し、その流量を返す。
int main() {
int V, E;
scanf("%d %d", &V, &E);
FordFulkerson< int > g(V);
for(int i = 0; i < E; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
g.add_edge(a, b, c);
}
printf("%d\n", g.max_flow(0, V - 1));
}*/
int main(){
ll w,n;
cin>>w>>n;
V J(n);
rep(i,n)cin>>J[i];
ll m;cin>>m;
V C(n);
rep(i,m)cin>>C[i];
FordFulkerson<ll> g(2*n+2*m+100);
rep(i,n)g.add_edge(0,i+1,1e18);
rep(i,n)g.add_edge(i+1,i+n+1,J[i]);
rep(i,m){
int q;cin>>q;
vector<bool> have(100);
rep(j,q){
int x;cin>>x;
x--;
have[x]=true;
}
rep(j,n){
if(have[j])continue;
g.add_edge(j+n+1,2*n+i+1,1e18);
}
}
rep(i,m)g.add_edge(2*n+1+i,2*n+m+1+i,C[i]);
rep(i,m)g.add_edge(2*n+m+1+i,2*n+2*m+1,1e18);
int k=g.max_flow(0,2*n+2*m+1);
// cout<<k<<endl;
if(k>=w){
cout<<"SHIROBAKO"<<endl;
}else{
cout<<"BANSAKUTSUKITA"<<endl;
}
}