AOJ 2429 まるかいて

Div1Easy以上Mid未満かなぁ、フローはほとんど解いたことが無いから難易度判別できない＞＜〜
重み付き二部最大マッチングです。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;


typedef long long ll;
const int MAX_V = 210;
const int INT_INF = 1<<30;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
struct edge {
	int to, cap, cost, rev;
};
int V;
vector<edge> G[MAX_V];
int h[MAX_V], dist[MAX_V];
int prevv[MAX_V], preve[MAX_V];

void add_edge(int from, int to, int cap, int cost) {
	G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
	G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1});
}

int min_cost_flow(int s, int t, int f) {
	int res = 0;
	fill_n(h, V, 0);
	while (f > 0) {
		priority_queue<P, vector<P>, greater<P>> que;
		fill_n(dist, V, INT_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 < G[v].size(); i++) {
				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] == INT_INF) {
			return -1;
		}
		for (int v = 0; v < V; v++) {
			h[v] += dist[v];
		}
		int d = f;
		for (int v = 0; 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;
}

const int MAX_N = 105;
int N;
int W[MAX_N][MAX_N], E[MAX_N][MAX_N];
bool F[MAX_N][MAX_N], F2[MAX_N][MAX_N];

int main(int argc, char *argv[]) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &(W[i][j]));
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &(E[i][j]));
		}
	}
	int min_f = 0, f = 0;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < N; j++) {
			F[i][j] = (s[j] == 'o');
			if (F[i][j]) {
				min_f = min(min_f, -E[i][j]);
				f += E[i][j];
			}
		}
	}
	min_f *= -1;
	V = (N+1)*2;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j]) {
				add_edge(i, N+j, 1, -E[i][j]+min_f);
			} else {
				add_edge(i, N+j, 1, W[i][j]+min_f);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		add_edge(N*2, i, 1, 0);
	}
	for (int i = 0; i < N; i++) {
		add_edge(N+i, N*2+1, 1, 0);
	}
	f += min_cost_flow(N*2, N*2+1, N);
	f -= min_f*N;
	int c = 0;
	vector<T> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (F[i][j] == G[i][j].cap) {
				c++;
				q.push_back(T(i, j, F[i][j]));
			}
		}
	}
	printf("%d\n%d\n", f, c);
	for (T t: q) {
		printf("%d %d %s\n", get<0>(t)+1, get<1>(t)+1, get<2>(t) ? "erase" : "write");
	} 
    return 0;
}