SRM 506 div1 med:SlimeXGrandSlimeAuto

問題読んだ直後は(これは解けないな…)と思っていたので解き方がわかった時はすごくテンション上がった。良い問題。

問題

TopCoder Statistics - Problem Statement

解法

いつも通り状態を保存するように深さ優先探索しても状態数が多すぎて間に合わない。

ということでいつも通りなんとか発想を逆転させて探索量を減らさなければならない(期待値問題とかだとよく期待値の線形性に持ち込まれますよね)。

今回の場合は「各districts[i]にたどり着くために各iに対してどの車を使うか,もしくは使わないか」と考えるのではなく,「各車を,どの移動の時に使うようにするか」と考えます。つまり,移動と車をどのようにマッチングするのが最適になるかをもとめる最小費用流問題に帰着します。

これがわかれば後は割とスッキリで,以下のようなグラフを考えれば良いです。コストの計算は予めワーシャルフロイドで計算しておけば良いでしょう。

topcoderの解説によりわかりやすい図があったのでそっちも貼っておきます。

const int INF = 1e9;

class minimumCostFlow {
public:
    minimumCostFlow(int V) : V(V) {
        G.resize(V);
        h.resize(V);
        dist.resize(V);
        prevv.resize(V);
        preve.resize(V);
    }
    void add_edge(int from, int to, int cap, int cost) {
        G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
        G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1});
    }
    // sからtへの流量fの最小費用流を求める
    // 流せない場合は-1を返す
    int min_cost_flow(int s, int t, int f) {
        int res = 0;
        fill(h.begin(), h.end(), 0);
        while (f > 0) {
            // ダイクストラ法を用いてhを更新する
            priority_queue<P, vector<P>, greater<P> > que;
            fill(dist.begin(), dist.end(), _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;
                for (int i = 0; i < (int)G[v].size(); i++) {
                    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) {
                // これ以上流せない
                return -1;
            }
            for (int v = 0; v < V; v++) h[v] += dist[v];

            // s-t間最短路に沿って目一杯流す
            int d = f;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, 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;
    }
private:
    typedef pair<int, int> P;
    struct edge {
        int to;
        int cap;
        int cost;
        int rev;
    };
    // 頂点数
    int V;
    // グラフの隣接リスト表現
    vector<vector<edge> > G;
    // ポテンシャル
    vector<int> h;
    // 最短距離
    vector<int> dist;
    // 直前の頂点と辺
    vector<int> prevv;
    vector<int> preve;
    const int _INF = 1e9;
};
int dp[55][55];

class SlimeXGrandSlimeAuto {
public:
    int travel(vector <int> cars, vector <int> districts, vector <string> roads, int inverseWalkSpeed, int inverseDriveSpeed) {
        int n = roads.size();
        vector<vi> d(n, vi(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = INF;
            }
            d[i][i] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char c = roads[i][j];
                if ('0' <= c && c <= '9') {
                    d[i][j] = (int)(c-'0') + 1;
                }
                if ('a' <= c && c <= 'z') {
                    d[i][j] = (int)(c-'a') + 11;
                }
                if ('A' <= c && c <= 'Z') {
                    d[i][j] = (int)(c-'A') + 37;
                }
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int m = districts.size();
        int p = cars.size();
        for (int i = 0; i < m-1; i++) {
            dp[i][p] = inverseWalkSpeed*d[districts[i]][districts[i+1]];
            for (int j = 0; j < p; j++) {
                dp[i][j] = inverseWalkSpeed * d[districts[i]][cars[j]] + inverseDriveSpeed * d[cars[j]][districts[i+1]];
            }
        }
        for (int j = 0; j < p; j++) {
            dp[m-1][j] = inverseWalkSpeed * d[0][cars[j]] + inverseDriveSpeed * d[cars[j]][districts[0]];
        }
        dp[m-1][p] = inverseWalkSpeed * d[0][districts[0]];
        int s = m+p+1, t = s+1, mugen = t+1, V = mugen+1;
        minimumCostFlow* mcf = new minimumCostFlow(V);
        for (int i = 0; i < m; i++) {
            mcf->add_edge(s, i, 1, 0);
            mcf->add_edge(i, mugen, 1, dp[i][p]);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < p; j++) {
                mcf->add_edge(i, j+m, 1, dp[i][j]);
            }
        }
        mcf->add_edge(mugen, t, INF, 0);
        for (int j = 0; j < p; j++) {
            mcf->add_edge(j+m, t, 1, 0);
        }
        int ret = (mcf->min_cost_flow(s, t, m));
        return ret;
    }
};