結果
問題 |
No.957 植林
|
ユーザー |
![]() |
提出日時 | 2019-12-20 23:19:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 895 ms / 2,000 ms |
コード長 | 2,685 bytes |
コンパイル時間 | 3,065 ms |
コンパイル使用メモリ | 206,276 KB |
最終ジャッジ日時 | 2025-01-08 13:46:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} template<typename T,bool directed> struct Dinic{ struct edge { int to; T cap; int rev; edge(){} edge(int to,T cap,int rev):to(to),cap(cap),rev(rev){} }; vector<vector<edge> > G; vector<int> level,iter; Dinic(){} Dinic(int n):G(n),level(n),iter(n){} int add_edge(int from,int to,T cap){ G[from].emplace_back(to,cap,G[to].size()); G[to].emplace_back(from,directed?0:cap,G[from].size()-1); return G[to].back().rev; } void bfs(int s){ fill(level.begin(),level.end(),-1); queue<int> que; level[s]=0; que.emplace(s); while(!que.empty()){ int v=que.front();que.pop(); for(int i=0;i<(int)G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[e.to]<0){ level[e.to]=level[v]+1; que.emplace(e.to); } } } } T dfs(int v,int t,T f){ if(v==t) return f; for(int &i=iter[v];i<(int)G[v].size();i++){ edge &e=G[v][i]; if(e.cap>0&&level[v]<level[e.to]){ T d=dfs(e.to,t,min(f,e.cap)); if(d==0) continue; e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } return 0; } T flow(int s,int t,T lim){ T fl=0; while(1){ bfs(s); if(level[t]<0||lim==0) break; fill(iter.begin(),iter.end(),0); while(1){ T f=dfs(s,t,lim); if(f==0) break; fl+=f; lim-=f; } } return fl; } T flow(int s,int t){ return flow(s,t,numeric_limits<T>::max()/2); } T cut(int s,int t,int x,int a){ static_assert(directed, "must be directed"); auto &e=G[x][a]; int y=e.to; T cr=G[y][e.rev].cap; if(cr==0) return e.cap=0; e.cap=G[y][e.rev].cap=0; T cap=cr-flow(x,y,cr); if(x!=s&&cap!=0) flow(x,s,cap); if(t!=y&&cap!=0) flow(t,y,cap); return cap; } T link(int s,int t,int x,int a,T f){ auto &e=G[x][a]; e.cap+=f; return flow(s,t,f); } }; //INSERT ABOVE HERE signed main(){ int h,w; cin>>h>>w; using ll = long long; Dinic<ll, true> G(h+w+2); int S=h+w; int T=S+1; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ int g; cin>>g; G.add_edge(i,h+j,g); G.add_edge(S,i,g); } } ll sum=0; for(int i=0;i<h;i++){ int r; cin>>r; sum+=r; G.add_edge(i,T,r); } for(int j=0;j<w;j++){ int c; cin>>c; sum+=c; G.add_edge(h+j,T,c); } cout<<sum-G.flow(S,T)<<endl; return 0; }