AOJ 2429

経路復元的なアレがあるフロー。フロー部分は簡単です。

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

typedef int Weight;
const Weight INF=99999999;

struct Edge{
	int dst,cap;Weight cost,rev;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

//srcからdstへ向かう容量cap,コストcostの辺をグラフに追加する
void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){
	G[src].push_back((Edge){dst,cap,cost,G[dst].size()});
	G[dst].push_back((Edge){src,0,-cost,G[src].size()-1});
}

//sからtへの流量fの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(Graph &G,int s,int t,int f){
	typedef pair<int,int> P;
	int res=0;
	int V=G.size();
	vector<Weight> h(V,0);
	vector<int> prevv(V);
	vector<int> preve(V);
	
	while(f>0){
		priority_queue<P,vector<P>,greater<P> > que;
		vector<Weight> dist(V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();que.pop();
			int v=p.second;
			if(dist[v]<p.first)continue;
			for(int i=0;i<(int)G[v].size();i++){
				Edge &e=G[v][i];
				if(e.cap>0&&dist[e.dst]>dist[v]+e.cost+h[v]-h[e.dst]){
					dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst];
					prevv[e.dst]=v;
					preve[e.dst]=i;
					que.push(P(dist[e.dst],e.dst));
				}
			}
		}
		if(dist[t]==INF){	
			return -1;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];

		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(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 E[100][100];
int W[100][100];
char str[100][102];
int D[100][100];
int R[10000];
int C[10000];
char ope[10001];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++)
			scanf("%d",&W[i][j]);
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++)
			scanf("%d",&E[i][j]);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	Graph g(2+a*2);
	for(int i=0;i<a;i++){
		add_edge(g,a*2,i,1,0);
		add_edge(g,i+a,a*2+1,1,0);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(str[i][j]=='.')D[i][j]+=W[i][j];
			for(int k=0;k<a;k++){
				if(j!=k&&str[i][k]=='o')D[i][j]+=E[i][k];
			}
	//		printf("%d ",D[i][j]);
		}//printf("\n");
	}
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++)
			add_edge(g,i,a+j,1,D[i][j]);
	int ret=min_cost_flow(g,a*2,a*2+1,a);
	printf("%d\n",ret);
	int n=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<g[i].size();j++){
			if(g[i][j].dst<a*2){
				if(g[i][j].cap==0&&str[i][g[i][j].dst-a]=='.'){
					R[n]=i;
					C[n]=g[i][j].dst-a;
					ope[n++]='w';
				}
				if(g[i][j].cap&&str[i][g[i][j].dst-a]=='o'){
					R[n]=i;
					C[n]=g[i][j].dst-a;
					ope[n++]='e';
				}
			}
		}
	}
	printf("%d\n",n);
	for(int i=0;i<n;i++){
		printf("%d %d ",R[i]+1,C[i]+1);
		if(ope[i]=='e')printf("erase\n");
		else printf("write\n");
	}
}