ACL1 C. Moving Pieces

考察

最小費用流の形にできそう、超頂点S,Tを用意してコマの開始位置へSから容量1コスト0の辺を張って、好きなところから1つずつ回収してTに送る容量1コスト0の辺を加える。
元のグリッドグラフ上では各頂点から右と下に容量無限(コマの個数でよい)コスト-1の辺を張る(ここで-1なのはパスの長さの和を最大化したいから)。
しかし、最小費用流が負辺があるのは少し厄介である。今回は明らかに負の閉路はない。負の辺に対応するには
1. グラフを変形して負辺を除去する
2. ポテンシャルの初期化をDijkstraではなくBellman-Fordを用いる

の2通りの方法があるが、今回は1を採用した。(理由: ベルマンフォードでポテンシャル初期化するライブラリを持っていない&ACLにもなかったため)

グラフの変形による負辺の除去は蟻本のコラムにある。少し複雑そうにも見えるが、基本的なアイデアは負の辺にあらかじめ目一杯流しておいて後で戻すである。流す量なども変形によって代わることに注意。

想定解&感想

想定解ではもっと綺麗に最小費用流の形に言い換えていて、この方法ではグラフに負の辺ははじめから現れない。
「パスの長さの和の最大化」として捉えるのではなく、「一番右下まで行ったときに比べてどれくらい損をしたか、の和を最小化」と捉えることですんなりと最小費用流で解ける。
グラフの変形もそこそこ面倒なのでBellman-Fordで間に合いそうな時用にライブラリ準備しておくべきだなぁ...と思った。

void solve() {
  int N, M;
  cin >> N >> M;
  vector<string> f(N);
  cin >> f;
  int s = N * M, t = N * M + 1;
  int S = N * M + 2, T = N * M + 3;
  atcoder::mcf_graph<int, int> g(T + 1);
  auto encode = [&](int i, int j) { return i * M + j; };
 
  int C = 0;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      if (f[i][j] == 'o') C++;
 
  g.add_edge(S, s, C, 0);
  g.add_edge(t, T, C, 0);
 
  int F = C;
  int geta = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (f[i][j] == '#') continue;
      int u = encode(i, j);
      g.add_edge(u, t, 1, 0);
      if (f[i][j] == 'o') g.add_edge(s, u, 1, 0);
      if (i + 1 < N && f[i + 1][j] != '#') {
        int v = encode(i + 1, j);
        geta -= C;
        F += C;
        g.add_edge(v, u, C, 1);
        g.add_edge(S, v, C, 0);
        g.add_edge(u, T, C, 0);
      }
      if (j + 1 < M && f[i][j + 1] != '#') {
        int v = encode(i, j + 1);
        geta -= C;
        F += C;
        g.add_edge(v, u, C, 1);
        g.add_edge(S, v, C, 0);
        g.add_edge(u, T, C, 0);
      }
    }
  }
  auto res = g.flow(S, T, F);
  cout << -res.second - geta << endl;
  assert(res.first == F);
  return;
}

okura diary

おもに競技プログラミングの日記

ACL1 C. Moving Pieces

考察

想定解&感想