結果

問題 No.177 制作進行の宮森あおいです！
ユーザー zeke
提出日時 2019-11-12 20:48:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,873 bytes
コンパイル時間 888 ms
コンパイル使用メモリ 94,840 KB
最終ジャッジ日時 2024-11-14 21:50:15
合計ジャッジ時間 1,294 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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

ソースコード

diff #
プレゼンテーションモードにする

/*
    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;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0