まるかいて (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);
	}
}