結果
問題 |
No.2713 Just Solitaire
|
ユーザー |
|
提出日時 | 2024-03-31 15:03:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,426 bytes |
コンパイル時間 | 2,333 ms |
コンパイル使用メモリ | 210,000 KB |
最終ジャッジ日時 | 2025-02-20 17:35:31 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#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'; }