2020-09-23

ACL Contest 1 C - Moving Pieces (青色, 600 点)

AtCoder AtCoder600点 ARC-like 二次元グリッドパズルフローグラフマッチング二部マッチング最小費用流問題操作ロボット多点を扱う問題前処理最短路問題 BFS 下駄を履かせて負辺除去グラフの辺数を削減する青色diff 【問題集】フローの入門割当問題駒(コマ)や石やコインを扱う問題穴や盤外に落とす問題典型要素を詰め合わせた教育的問題グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る壁マス

フローって確かに天才パズルな問題はすごく天才的なんだけど、典型的な問題もたくさんある！

問題へのリンク

問題概要

下図のような $H \times W$ の盤面が与えられる。盤面は通路 ('.') と壁 ('#') がある。いくつかの通路にはコマ ('o') が配置されている。

コマは下方向と右方向にのみ、通路にのみ動かすことができる (コマがすでにあるマスにも動かせない)。コマがまったく動かせなくなる状態になるまでにコマを動かす距離の長さとして考えられる最大値を求めよ。

o..
...
o.#

解法

$1 \le N, M \le 50$
駒の個数は $100$ 以下

考えたこと

フローの典型の一つである「割当問題・二部マッチング」について慣れがあると、これはすぐ見える！！！

一般に、「男」と「女」みたいな 2 つのカテゴリ間の割当 (マッチング) を最適化する問題は、フローで扱える。

qiita.com

今回は、

駒
(各駒を最終的に動かす) 通路マス

との割当問題と考えることができる。よって左側に各駒に対応するノード、右側に通路マスに対応するノードを配置して、それらの間のコストを「移動距離」にして重み最大のマッチングを求めれば OK。

その問題は最小費用流に帰着できる。最小化問題の形にしなければならないので、移動距離を -1 倍する。このままでも解けるけど、さらに重みが負だとあまり都合がよくないので、大きめの重みを全ペアに一律に足して下駄を履かせた。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// edge class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct Edge {
    int rev, from, to, id;
    FLOWTYPE cap, icap;
    COSTTYPE cost;
    Edge(int r, int f, int t, FLOWTYPE ca, COSTTYPE co, int id = -1) :
        rev(r), from(f), to(t), cap(ca), icap(ca), cost(co), id(id) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0)
            return s << E.from << "->" << E.to <<
                '(' << E.cap << ',' << E.cost << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE, COSTTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE, COSTTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE, COSTTYPE> &redge(const Edge<FLOWTYPE, COSTTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
        list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id));
        list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, 0, -cost));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
        list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id));
        list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, cap, cost, id));
    }

    friend ostream& operator << (ostream& s, const Graph& G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << ":";
            for (auto e : G.list[i]) s << " " << e;
            s << endl;
        }
        return s;
    }   
};

// min-cost flow (by primal-dual)
template<class FLOWTYPE, class COSTTYPE> COSTTYPE MinCostFlow(Graph<FLOWTYPE, COSTTYPE> &G, int s, int t, FLOWTYPE f) {
    int n = (int)G.size();
    vector<COSTTYPE> pot(n, 0), dist(n, -1);
    vector<int> prevv(n), preve(n);
    COSTTYPE res = 0;
    while (f > 0) {
        priority_queue<pair<COSTTYPE,int>, vector<pair<COSTTYPE,int> >, greater<pair<COSTTYPE,int> > > que;
        dist.assign(n, -1);
        dist[s] = 0;
        que.push(make_pair(0,s));
        while(!que.empty()) {
            pair<COSTTYPE,int> p = que.top();
            que.pop();
            int v = p.second;
            if (dist[v] < p.first) continue;
            for (int i = 0; i < G[v].size(); ++i) {
                auto e = G[v][i];
                if (e.cap > 0 && (dist[e.to] < 0 || dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to])) {
                    dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.push(make_pair(dist[e.to], e.to));
                }
            }
        }
        if (dist[t] < 0) return -1;
        for (int v = 0; v < n; ++v) pot[v] += dist[v];
        FLOWTYPE d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += pot[t] * d;
        for (int v = t; v != s; v = prevv[v]) {
            Edge<FLOWTYPE,COSTTYPE> &e = G[prevv[v]][preve[v]];
            Edge<FLOWTYPE,COSTTYPE> &re = G.redge(e);
            e.cap -= d;
            re.cap += d;
        }
    }
    return res;
}

using pint = pair<int,int>;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> fi(N);
    for (int i = 0; i < N; ++i) cin >> fi[i];

    map<pint, int> koma;
    int iter = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (fi[i][j] == 'o') 
                koma[pint(i, j)] = iter++;
        }
    }
    int K = koma.size();
    int R = N * M;
    vector<vector<int>> dist(K, vector<int>(R, -1));
    for (auto it : koma) {
        int i = it.second;
        int sx = it.first.first, sy = it.first.second;
        queue<pint> que;
        vector<vector<int>> dp(N, vector<int>(M, -1));
        dp[sx][sy] = 0;
        que.push({sx, sy});
        while (!que.empty()) {
            auto p = que.front();
            int x = p.first, y = p.second;
            que.pop();
            for (int dir = 0; dir < 2; ++dir) {
                int nx = p.first + dx[dir];
                int ny = p.second + dy[dir];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (fi[nx][ny] == '#') continue;
                if (dp[nx][ny] != -1) continue;

                dp[nx][ny] = dp[x][y] + 1;
                que.push(pint(nx, ny));
            }
        }
        for (int h = 0; h < N; ++h) {
            for (int w = 0; w < M; ++w) {
                dist[i][h*M + w] = dp[h][w];
            }
        }
    }

    int GETA = 1000;
    Graph<int,int> G(K + R + 2);
    int s = K + R, t = K + R + 1;
    for (int l = 0; l < K; ++l) {
        G.addedge(s, l, 1, 0);
    }
    for (int r = 0; r < R; ++r) {
        G.addedge(r + K, t, 1, 0);
    }
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < R; ++j) {
            if (dist[i][j] == -1) continue;
            G.addedge(i, j + K, 1, GETA - dist[i][j]);
        }
    }
    long long res = MinCostFlow(G, s, t, K);
    res = GETA * K - res;
    cout << res << endl;
}