まるかいて (AOJ2429)
どうみてもフロー
コストを行にわけて考えるとよい(各行でひとつしか選ばれないので)
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef pair<int,int> P; struct edge{ int to,cap,cost,rev; edge(int to,int cap,int cost,int rev) :to(to),cap(cap),cost(cost),rev(rev){} }; const int MAX_V=202,INF=1e9; int V; vector<edge> G[MAX_V]; int h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V]; void add_edge(int from,int to,int cap,int cost){ edge e1=edge(to,cap,cost,G[to].size()),e2=edge(from,0,-cost,G[from].size()); G[from].pb(e1),G[to].pb(e2); } int min_cost_flow(int s,int t,int f){ int res=0; fill(h,h+V,0); while(f>0){ priority_queue<P,vector<P>,greater<P> > que; fill(dist,dist+V,INF); dist[s]=0; que.push(P(0,s)); while(!que.empty()){ P p=que.top(); que.pop(); int v=p.sc; if(dist[v]<p.fs) continue; rep(i,G[v].size()){ edge &e=G[v][i]; if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){ dist[e.to]=dist[v]+e.cost+h[v]-h[e.to]; prevv[e.to]=v; preve[e.to]=i; que.push(P(dist[e.to],e.to)); } } } if(dist[t]==INF) return -1; rep(v,V) h[v]+=dist[v]; int d=f; for(int v=t;v!=s;v=prevv[v]){ chmin(d,G[prevv[v]][preve[v]].cap); } f-=d; res+=d*h[t]; for(int v=t;v!=s;v=prevv[v]){ edge &e=G[prevv[v]][preve[v]]; e.cap-=d; G[v][e.rev].cap+=d; } } return res; } int main(){ int N; int w[100][100],e[100][100]; string s[100]; cin>>N; rep(i,N) rep(j,N) cin>>w[i][j]; rep(i,N) rep(j,N) cin>>e[i][j]; rep(i,N) cin>>s[i]; int S=2*N,T=2*N+1; V=2*N+2; rep(i,N) add_edge(S,i,1,0); rep(i,N) add_edge(N+i,T,1,0); rep(i,N) rep(j,N){ int c=0; rep(k,N){ if(k==j){ if(s[i][k]=='.') c+=w[i][k]; }else{ if(s[i][k]=='o') c+=e[i][k]; } } add_edge(i,N+j,1,c); } int f=min_cost_flow(S,T,N); cout<<f<<endl; bool is[100][100]={}; rep(v,N){ for(edge e:G[v]){ int u=e.to; if(u<2*N){ is[v][u-N]=(e.cap==0); } } } int c=0; rep(i,N) rep(j,N) if((s[i][j]=='o')^is[i][j]) c++; cout<<c<<endl; rep(i,N) rep(j,N){ if((s[i][j]=='o')&&!is[i][j]) printf("%d %d erase\n",i+1,j+1); if((s[i][j]=='.')&&is[i][j]) printf("%d %d write\n",i+1,j+1); } }