結果

問題 No.177 制作進行の宮森あおいです！
ユーザー shiomusubi496shiomusubi496
提出日時 2021-09-05 11:29:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,637 bytes
コンパイル時間 2,642 ms
コンパイル使用メモリ 213,152 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-21 17:51:01
合計ジャッジ時間 2,891 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 5 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 11 ms
5,248 KB
testcase_10 AC 15 ms
5,248 KB
testcase_11 AC 13 ms
5,248 KB
testcase_12 AC 8 ms
5,248 KB
testcase_13 AC 2 ms
5,248 KB
testcase_14 AC 1 ms
5,248 KB
testcase_15 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void MaxFlowGraph::add_edge(int, int, int)':
main.cpp:10:38: warning: narrowing conversion of '(&((MaxFlowGraph*)this)->MaxFlowGraph::G.std::vector<std::vector<MaxFlowGraph::edge> >::operator[](((std::vector<std::vector<MaxFlowGraph::edge> >::size_type)b)))->std::vector<MaxFlowGraph::edge>::size()' from 'std::vector<MaxFlowGraph::edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   10 |         G[a].push_back({b,c,G[b].size()});
      |                             ~~~~~~~~~^~
main.cpp:11:40: warning: narrowing conversion of '((&((MaxFlowGraph*)this)->MaxFlowGraph::G.std::vector<std::vector<MaxFlowGraph::edge> >::operator[](((std::vector<std::vector<MaxFlowGraph::edge> >::size_type)a)))->std::vector<MaxFlowGraph::edge>::size() - 1)' from 'std::vector<MaxFlowGraph::edge>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   11 |         G[b].push_back({a,0,G[a].size()-1});
      |                             ~~~~~~~~~~~^~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
constexpr int INF=1e9;
struct MaxFlowGraph{
    struct edge{int to,cap,rev;};
    MaxFlowGraph(int n):G(n),_n(n){}
    void add_edge(int a,int b,int c){
        assert(0<=a && a<_n);
        assert(0<=b && b<_n);
        G[a].push_back({b,c,G[b].size()});
        G[b].push_back({a,0,G[a].size()-1});
    }
    int flow(int s,int t){
        int res=0;
        while(true){
            used.assign(_n,false);
            int fw=dfs(s,t,INF);
            if(fw==0)break;
            res+=fw;
        }
        return res;
    }
    private:
    int _n;
    std::vector<std::vector<edge>> G;
    std::vector<bool> used;
    int dfs(int v,int t,int f){
        if(v==t)return f;
        used[v]=true;
        for(edge &e:G[v]){
            if(used[e.to] || e.cap==0) continue;
            int fw=dfs(e.to,t,min(f,e.cap));
            if(fw==0) continue;
            e.cap-=fw;
            G[e.to][e.rev].cap+=fw;
            return fw;
        }
        return 0;
    }
};
int main(){
    int W,N,M; cin>>W>>N;
    vector<int> J(N);
    for(int i=0;i<N;i++)cin>>J[i];
    cin>>M;
    vector<int> C(M);
    for(int i=0;i<M;i++)cin>>C[i];
    MaxFlowGraph G(N+M+2);
    int s=N+M,t=s+1;
    for(int i=0;i<N;i++)G.add_edge(s,i,J[i]);
    for(int i=0;i<M;i++)G.add_edge(i+N,t,C[i]);
    for(int i=0;i<M;i++){
        vector<bool> A(N,true);
        int Q; cin>>Q;
        for(int j=0;j<Q;j++){
            int X; cin>>X;
            A[X-1]=false;
        }
        for(int j=0;j<N;j++){
            if(A[j])G.add_edge(j,N+i,W);
        }
    }
    puts(G.flow(s,t)<W?"BANSAKUTSUKITA":"SHIROBAKO");
}
0