けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

ACL Contest 1 C - Moving Pieces (600 点)

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

問題へのリンク

問題概要

下図のような  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;
}

他の解法

これ確かに!!!となったのだけど、全駒と全通路について辺をはるのではなく、グリッドの隣接しているところに辺を這わせるようなネットワークを作る方法もある。そっちの方がネットワークの辺の本数が少なくなって計算量も改善される!