結果
問題 | No.2713 Just Solitaire |
ユーザー | Nzt3 |
提出日時 | 2024-03-31 15:03:38 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,426 bytes |
コンパイル時間 | 2,226 ms |
コンパイル使用メモリ | 217,612 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 20:12:58 |
合計ジャッジ時間 | 3,060 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 1 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,820 KB |
testcase_09 | AC | 1 ms
6,816 KB |
testcase_10 | AC | 1 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,820 KB |
testcase_12 | AC | 1 ms
6,816 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 1 ms
6,816 KB |
testcase_16 | AC | 1 ms
6,816 KB |
testcase_17 | AC | 1 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 2 ms
6,816 KB |
testcase_21 | AC | 1 ms
6,820 KB |
testcase_22 | AC | 1 ms
6,820 KB |
testcase_23 | AC | 2 ms
6,816 KB |
testcase_24 | AC | 2 ms
6,820 KB |
testcase_25 | AC | 2 ms
6,816 KB |
testcase_26 | AC | 2 ms
6,816 KB |
testcase_27 | AC | 2 ms
6,816 KB |
testcase_28 | AC | 2 ms
6,820 KB |
testcase_29 | AC | 2 ms
6,816 KB |
testcase_30 | AC | 2 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,816 KB |
testcase_32 | AC | 2 ms
6,816 KB |
testcase_33 | AC | 2 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; namespace Lib{ struct mf_graph{ struct _edge{ int to,rev; ll cap; }; struct edge{ int from,to; ll cap,flow; }; vector<array<int,2>> pos; vector<vector<_edge>> graph; unsigned v_size; mf_graph (int n): graph(n),v_size(n){} void add_edge(int from,int to,ll cap){ pos.push_back({from,(int)graph[from].size()}); graph[from].push_back(_edge({to,(int)graph[to].size(),cap})); graph[to].push_back(_edge({from,(int)graph[from].size()-1,0})); } ll flow(int s,int t){ ll ret=0; vector lev(v_size,-1); auto bfs = [&](int s){ fill(lev.begin(),lev.end(),-1); queue<int>q; lev[s]=0; q.push(s); while(!q.empty()){ int v=q.front(); q.pop(); for(auto e:graph[v]){ if(e.cap>0&&lev[e.to]<0){ lev[e.to]=lev[v]+1; q.push(e.to); } } } }; vector iter(v_size,0); auto dfs = [&](auto self,int v,ll 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&&lev[v]<lev[e.to]){ ll d=self(self,e.to,min(f,e.cap)); if(d>0){ e.cap-=d; graph[e.to][e.rev].cap+=d; return d; } } } return 0ll; }; while(1){ bfs(s); if(lev[t]<0)return ret; fill(iter.begin(),iter.end(),0); ll f=0; while((f=dfs(dfs,s,LLONG_MAX))>0){ ret+=f; } } } vector<edge> edges(){ vector<edge>ret; for(auto i:pos){ auto e=graph[i[0]][i[1]],re=graph[e.to][e.rev]; ret.push_back(edge({i[0],e.to,e.cap+re.cap,re.cap})); } return ret; } }; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin>>N>>M; Lib::mf_graph G(2+N+M); for(int i=0;i<N;i++){ ll A; cin>>A; G.add_edge(i+2,1,A); } vector B(M,0ll); for(ll &i:B)cin>>i; ll inf_flow=1e18; for(int i=0;i<M;i++){ int K; cin>>K; G.add_edge(0,2+N+i,B[i]); for(int j=0;j<K;j++){ int C; cin>>C; G.add_edge(2+N+i,2+C-1,inf_flow); } } ll ans=accumulate(B.begin(),B.end(),0ll)-G.flow(0,1); cout<<ans<<'\n'; }