AOJ 2429 marukaite
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429
のグリッドがある。各マスは初期状態でo
が書かれているか書かれていないかのどちらか一方である。各マスに対して、空白のときに書くコストと既にあるo
を消すコストが与えられる。同じ行/列にo
がちょうど1個になるように書いたり消したりするときの最小値をもとめよ。
解法
(2時間くらい考えて解けなかったので他人の答えを見ました。)
最小費用量で解ける。
個の頂点 を作り、マス に書くことに正のコスト、消すことに負のコストを持たせて容量1の辺 を張る。さらに容量1コスト0の辺 を張り、 から へ容量 のフローを流したときの最小費用を求める。
初期状態のコストをその状態から何もない状態にするのに必要なコストとし、そこに上で求めた最小費用を足すと答えになる。
int n; Weight W[128][128], E[128][128]; char f[128][128]; void solve(){ Weight C=0; rep(i,n)rep(j,n){ if(f[i][j]=='o')C+=E[i][j]; } Graph g(n*2+2); int s=n*2, t=n*2+1; rep(i,n){ add_edge(g,s,i,1,0); add_edge(g,i+n,t,1,0); } rep(i,n)rep(j,n){ if(f[i][j]=='o'){ add_edge(g,i,j+n,1,-E[i][j]); }else{ add_edge(g,i,j+n,1,W[i][j]); } } printf("%d\n",C+primal_dual(g,s,t,n)); static int ans[10000][3]; int cnt=0; rep(i,g.size()){ rep(j,g[i].size()){ auto & e=g[i][j]; if(e.is_rev || e.cost==0) continue; if(f[e.src][e.dst-n]=='o' && e.cap!=0){ cnt++; ans[cnt][0]=e.src+1; ans[cnt][1]=e.dst-n+1; ans[cnt][2]=0; }else if(f[e.src][e.dst-n]=='.' && e.cap==0){ cnt++; ans[cnt][0]=e.src+1; ans[cnt][1]=e.dst-n+1; ans[cnt][2]=1; } } } printf("%d\n",cnt); rep(i,cnt){ printf("%d %d %s\n",ans[i][0],ans[i][1],ans[i][2]==0 ? "erase" : "write"); } } int main(){ scanf("%d",&n); rep(i,n)rep(j,n){ scanf("%d",&W[i][j]); } rep(i,n)rep(j,n){ scanf("%d",&E[i][j]); } rep(i,n){ scanf("%s",f[i]); } solve(); }