AOJ 2429 marukaite - ferinの競プロ帳

考えたこと

解説を見た。

最小費用流を流すところは書けたが操作の復元に手間取った…最小費用流を行ったあと、容量が0の辺が存在すればその辺には流れたといえる。つまりR_iからC_jへの辺の容量が0であれば(i, j)は最終的に'o'であるといえる。よって最初の盤面と最終的な盤面を比較して異なる座標に操作を行ったといえる。

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAX_V 10000
struct edge { int to, cap, cost, rev; };

int V;
vector<edge> G[MAX_V];
int dist[MAX_V], prevv[MAX_V], preve[MAX_V];

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

int min_cost_flow(int s, int t, int f) {
  int res = 0;
  while(f > 0) {
    fill(dist, dist+V, INF);
    dist[s] = 0;
    bool update = true;
    while(update) {
      update = false;
      REP(v, V) {
        if(dist[v] == INF) continue;
        REP(i, G[v].size()) {
          edge &e = G[v][i];
          if(e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
            dist[e.to] = dist[v] + e.cost;
            prevv[e.to] = v;
            preve[e.to] = i;
            update = true;
          }
        }
      }
    }
    if(dist[t] == INF) return -1;

    int d = f;
    for(int v = t; v != s; v = prevv[v]) {
      chmin(d, G[prevv[v]][preve[v]].cap);
    }
    f -= d;
    res += d * dist[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 w[105][105], e[105][105];
string s[105], t[105];
signed main(void)
{
  int n;
  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];
  REP(i, n) t[i] = string(n, '.');

  // 'o'の位置のeraseコストの和を求める
  int sum = 0;
  REP(i, n) REP(j, n) if(s[i][j] == 'o') sum += e[i][j];

  // supersource:0, supersink:1, 行:2からn+1, 列:n+2から2*n+1
  V = 2*n+2;
  REP(i, n) add_edge(0, i+2, 1, 0);
  REP(i, n) add_edge(n+2+i, 1, 1, 0);
  REP(i, n) REP(j, n) {
    if(s[i][j] == 'o') {
      add_edge(i+2, j+n+2, 1, -e[i][j]);
    } else {
      add_edge(i+2, j+n+2, 1, w[i][j]);
    }
  }

  cout << sum + min_cost_flow(0, 1, n) << endl;

  // capが0の辺は使用している→最終盤面で'o'
  FOR(i, 2, n+2) for(edge e: G[i]) {
    if(e.cap == 0 && n+2 <= e.to && e.to < 2*n+2) {
      t[i-2][e.to-n-2] = 'o';
    }
  }

  // 最初の盤面から変化していればその座標は操作している
  vector<PII> ans;
  REP(i, n) REP(j, n) {
    if(s[i][j] == t[i][j]) continue;
    ans.PB({i, j});
  }

  cout << ans.size() << endl;
  for(auto i: ans) {
    cout << i.first+1 << " " << i.second+1;
    if(s[i.first][i.second] == '.') {
      cout << " write" << endl;
    } else {
      cout << " erase" << endl;
    }
  }

  return 0;
}