本番ずっと問題文誤読して「サンプル合わない…」とぼやいてた。
https://atcoder.jp/contests/abc225/tasks/abc225_g
問題
H*Wのグリッドが与えられる。
各セルにはスコアが振られている。
このうち、一部のセルに×マークを付けたい。
×マークを付けるために斜めの線を引かなければいけないが、1本あたりコストがCかかる。
ただ、斜めに位置するとセル間はまとめて1本の線で複数セルを構成する×マークの線を賄うことができる。
なお、×マークを構成する2本の斜め線のうち、片方だけ引いた状態のセルは許容されない。
×マークを付けたセルのスコアの総和から、線を引くコストを引いた値の最大値を求めよ。
解法
Project Selection Problemに持ち込む。
各セル、×マークを付けるか付けないかの状態を考えよう。
- ×マークを付けると、セルのスコア分得する。
- 左上マスに×マークがついていないとき、そのマスに×マークを付けるにはコストがCかかる
- 右上マスに×マークがついていないとき、そのマスに×マークを付けるにはコストがCかかる
と考えるとProject Selection Problemになるので最大フローで解くことができる。
int H,W; ll C,A[101][101]; template<class V> class MaxFlow_dinic { public: struct edge { ll to,reve;V cap;}; static const ll MV = 121000; vector<edge> E[MV]; ll itr[MV],lev[MV]; void add_edge(ll x,ll y,V cap,bool undir=false) { E[x].push_back((edge){y,(ll)E[y].size(),cap}); E[y].push_back((edge){x,(ll)E[x].size()-1,undir?cap:0}); } void bfs(ll cur) { MINUS(lev); queue<ll> q; lev[cur]=0; q.push(cur); while(q.size()) { ll v=q.front(); q.pop(); FORR(e,E[v]) if(e.cap>0 && lev[e.to]<0) lev[e.to]=lev[v]+1, q.push(e.to); } } V dfs(ll from,ll to,V cf) { if(from==to) return cf; for(;itr[from]<E[from].size();itr[from]++) { edge* e=&E[from][itr[from]]; if(e->cap>0 && lev[from]<lev[e->to]) { V f=dfs(e->to,to,min(cf,e->cap)); if(f>0) { e->cap-=f; E[e->to][e->reve].cap += f; return f; } } } return 0; } V maxflow(ll from, ll to) { V fl=0,tf; while(1) { bfs(from); if(lev[to]<0) return fl; ZERO(itr); while((tf=dfs(from,to,numeric_limits<V>::max()))>0) fl+=tf; } } }; MaxFlow_dinic<ll> mf; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>C; ll sum=0; //利益 FOR(y,H) FOR(x,W) { cin>>A[y][x]; sum+=A[y][x]; mf.add_edge(10000,y*100+x,A[y][x]); if(y==0||x==0) { mf.add_edge(y*100+x,10001,C); } else { mf.add_edge(y*100+x,(y-1)*100+(x-1),C); } if(y==0||x+1==W) { mf.add_edge(y*100+x,10001,C); } else { mf.add_edge(y*100+x,(y-1)*100+(x+1),C); } } cout<<sum-mf.maxflow(10000,10001)<<endl; }
まとめ
本番中、×マークのうち片方だけつけても良いと勘違いしてました…。