まるかいて http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2429

aoj2429_WA.cpp

// 「行に'o'が1つになるためのコスト」を考えるだけではだめ？
// あるマスと同じ行・列を全部消すコストを考えるとマスごとに排反にならない　いかんせん

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(_v) for(auto _x:_v){cout<<_x<<" ";}cout<<endl
#define printVS(_vs) for(auto _x : _vs){cout << _x << endl;}
#define printVV(_vv) for(auto _v:_vv){for(auto _x:_v){cout<<_x<<" ";}cout<<endl;}
#define printP(_p) cout << _p.first << " " << _p.second << endl
#define printVP(_vp) for(auto _p : _vp) printP(_p);

typedef long long ll;
// typedef pair<int, int> Pii;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

const int INF = 99999999;
const int MAX_V = 210;

struct edge { int to, cap, cost, rev; };

int V;
vector<edge> G[MAX_V];
int h[MAX_V];                   // potential
int dist[MAX_V];
int prevv[MAX_V], preve[MAX_V]; // privious vertex, edge

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

// get min cost flow from s to t
// if we cannot flow f, then return -1
int min_cost_flow(int s, int t, int f) {
    int res = 0;
    fill(h, h + V, 0);
    while (f > 0) {
        // update h by dijkstra
        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.second;
            if (dist[v] < p.first) 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) {
            // no more flow
            return -1;
        }
        rep(v, V) h[v] += dist[v];

        // flow as much as possible along the minimum path from s to t
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, (int)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;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    cin >> n;
    V = 2 * n + 2;
    vvi write(n, vi(n));
    rep(i, n) rep(j, n) cin >> write[i][j];
    vvi erase(n, vi(n));
    rep(i, n) rep(j, n) cin >> erase[i][j];
    vector<string> field(n);
    rep(i, n) cin >> field[i];

    const int s = 2 * n;
    const int t = s + 1;
    rep(i, n) {
        add_edge(s, i, 1, 0);
    }
    rep(j, n) {
        add_edge(j + n, t, 1, 0);
    }

    rep(i, n) {
        rep(j, n) {
            int cost = 0;
            if (field[i][j] == '.') cost += write[i][j];
            rep(k, n) {
                if (k == j) continue;
                if (field[i][k] == 'o') cost += erase[i][j];
            }
            add_edge(i, j + n, 1, cost);
        }
    }

    int mincost = min_cost_flow(s, t, n);
    vector<string> ans;
    vector<int> selected(n, false);
    rep(i, n) {
        for (auto e : G[i]) {
            if (n <= e.to && e.to < 2 * n && e.cap == 0) {
                int j = e.to - n;
                selected[i] = j;
                if (field[i][j] == '.') {
                    ans.emplace_back(to_string(i + 1) + " " + to_string(j + 1) + " write");
                }
            }
        }
    }

    rep(i, n) {
        rep(j, n) {
            if (field[i][j] == 'o' && j != selected[i]) {
                ans.emplace_back(to_string(i + 1) + " " + to_string(j + 1) + " erase");
            }
        }
    }

    cout << mincost << endl;
    cout << ans.size() << endl;
    for (auto str : ans) {
        cout << str << endl;
    }

}