東京大学プログラミングコンテスト2011: K. 巡回セールスマン問題

,

AtCoderに提出したらなぜかテストケースが$0$個で自明なACが出る状態になってた。

solution

ほとんど木なので上手くやる。荒く見積もって$O(M \log N + (M - N)^3 + N^2)$。

$|E| \le |V| + 500$という制約によりほとんど木である。 頂点$1$を根として最短経路による木を張り、高々$501$本ある余った辺を覚えておく。 そのような辺の始点と終点は高々$1002$点であり、これに頂点$1$を加え、他の頂点と区別しておく。 そのような頂点のみで全点対間の最短距離を求める。 この情報ともに$1, 2, 3, \dots$と巡回をする。 頂点$i$から$i+1$へ移動するときには、$i$の下側の近い区別された頂点から$i+1$の上側の一番近い区別された頂点へ、あらかじめ求めておいた最短距離で移動するとすればよい。 上側の頂点は一意だが下側の頂点は一意ではないので、これは間に合うことを信じて全て全て舐める。

注意:

  • 巡回は可能だとは限らないのでだめな場合は適当に落とす
  • 多重辺はありうるので潰しておく
  • LCAで$O(\log N)$が乗ると間に合わないので https://www.slideshare.net/yumainoue965/lca-and-rmq を読んで$O(1)$を書く
  • 上のように理解をして通しはしたが何か勘違いしてそう。下側の区別された頂点も一意だったのでは

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void chmin(T & a, T const & b) { a = min(a, b); }

vector<int> dijkstra(vector<vector<pair<int, int> > > const & g, int root) {
    vector<int> dist(g.size(), INT_MAX);
    priority_queue<pair<int, int> > que;
    dist[root] = 0;
    que.emplace(- dist[root], root);
    while (not que.empty()) {
        int dist_i; int i; tie(dist_i, i) = que.top(); que.pop();
        if (dist[i] < - dist_i) continue;
        for (auto it : g[i]) {
            int j; int cost; tie(j, cost) = it;
            if (- dist_i + cost < dist[j]) {
                dist[j] = - dist_i + cost;
                que.emplace(dist_i - cost, j);
            }
        }
    }
    return dist;
}

vector<vector<int> > warshall_floyd(vector<vector<pair<int, int> > > const & g) {
    int n = g.size();
    vector<vector<int> > dist(n, vector<int>(n, INT_MAX));
    REP (i, n) {
        dist[i][i] = 0;
        for (auto edge : g[i]) {
            int j, cost; tie(j, cost) = edge;
            dist[i][j] = cost;
        }
    }
    REP (k, n) {
        REP (i, n) if (dist[i][k] != INT_MAX) {
            REP (j, n) if (dist[k][j] != INT_MAX) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    return dist;
}

template <class Monoid>
struct sparse_table {
    typedef typename Monoid::underlying_type underlying_type;
    vector<vector<underlying_type> > table;
    Monoid mon;
    sparse_table() = default;
    sparse_table(vector<underlying_type> const & data, Monoid const & a_mon = Monoid())
            : mon(a_mon) {
        int n = data.size();
        int log_n = 32 - __builtin_clz(n);
        table.resize(log_n, vector<underlying_type>(n, mon.unit()));
        table[0] = data;
        for (int k = 0; k < log_n-1; ++ k) {
            for (int i = 0; i < n; ++ i) {
                table[k+1][i] = mon.append(table[k][i], i + (1ll<<k) < n ? table[k][i + (1ll<<k)] : mon.unit());
            }
        }
    }
    underlying_type range_concat(int l, int r) const {
        assert (0 <= l and l <= r and r <= table[0].size());
        if (l == r) return mon.unit();
        int k = 31 - __builtin_clz(r - l);  // log2
        return mon.append(table[k][l], table[k][r - (1ll<<k)]);
    }
};
struct indexed_min_monoid {
    typedef pair<int, int> underlying_type;
    underlying_type unit() const { return { INT_MAX, INT_MAX }; }
    underlying_type append(underlying_type a, underlying_type b) const { return min(a, b); }
};
struct lowest_common_ancestor {
    sparse_table<indexed_min_monoid> table;
    vector<int> index;
    lowest_common_ancestor() = default;
    lowest_common_ancestor(int root, vector<vector<int> > const & g) {
        vector<pair<int, int> > tour;
        index.assign(g.size(), -1);
        function<void (int, int, int)> go = [&](int i, int parent, int depth) {
            index[i] = tour.size();
            tour.emplace_back(depth, i);
            for (int j : g[i]) if (j != parent) {
                go(j, i, depth + 1);
                tour.emplace_back(depth, i);
            }
        };
        go(root, -1, 0);
        table = sparse_table<indexed_min_monoid>(tour);
    }
    int operator () (int x, int y) const {
        x = index[x];
        y = index[y];
        if (x > y) swap(x, y);
        return table.range_concat(x, y + 1).second;
    }
};

ll solve(int n, int m, vector<vector<pair<int, int> > > & g) {

    // erase duplicated edges
    REP (i, n) {
        sort(ALL(g[i]));
        g[i].erase(unique(ALL(g[i]), [&](pair<int, int> e1, pair<int, int> e2) {
            return e1.first == e2.first;
        }), g[i].end());
    }

    // calculate shortest-paths and check the possibility
    constexpr int root = 0;
    vector<int> dist_root = dijkstra(g, root);
    if (count(ALL(dist_root), INT_MAX)) {
        return -1;
    }
    vector<vector<pair<int, int> > > rev_g(n);
    REP (i, n) {
        for (auto edge : g[i]) {
            int j, cost; tie(j, cost) = edge;
            rev_g[j].emplace_back(i, cost);
        }
    }
    auto rev_dist_root = dijkstra(rev_g, root);
    if (count(ALL(rev_dist_root), INT_MAX)) {
        return -1;
    }

    // make a shortest-path tree; collect the unused edges
    vector<vector<int> > children(n);
    vector<int> parent(n, -1);
    vector<vector<pair<int, int> > > unused_edges(n);
    REP (i, n) {
        for (auto edge : g[i]) {
            int j, cost; tie(j, cost) = edge;
            if (dist_root[i] + cost == dist_root[j] and parent[j] == -1) {
                children[i].push_back(j);
                parent[j] = i;
            } else {
                unused_edges[i].emplace_back(j, cost);
            }
        }
    }

    // select and reorder distinguished vertices
    map<int, int> distinguished;
    auto distinguished_insert = [&](int i) {
        if (not distinguished.count(i)) {
            distinguished.emplace(i, distinguished.size());
        }
    };
    distinguished_insert(0);
    REP (i, n) {
        if (not unused_edges[i].empty()) {
            distinguished_insert(i);
        }
        for (auto edge : unused_edges[i]) {
            int j = edge.first;
            distinguished_insert(j);
        }
    }

    // compute distances for all distinguished vertices; find the lowest distinguished ancestors for each vertex
    vector<vector<pair<int, int> > > h(distinguished.size());
    REP (i, n) {
        for (auto edge : unused_edges[i]) {
            int j, cost; tie(j, cost) = edge;
            h[distinguished[i]].emplace_back(distinguished[j], cost);
        }
    }
    vector<int> ancestor(n, -1);
    function<void (int, int)> go = [&](int i, int last) {
        if (distinguished.count(i)) {
            if (last != -1) {
                h[distinguished[last]].emplace_back(distinguished[i], dist_root[i] - dist_root[last]);
            }
            last = i;
        }
        ancestor[i] = last;
        for (int j : children[i]) {
            go(j, last);
        }
    };
    go(root, -1);
    auto dist = warshall_floyd(h);

    // prepare the lca for the shortest-path tree
    lowest_common_ancestor lca(root, children);

    // compute the result
    ll result = 0;
    REP (i, n) {
        int j = (i + 1) % n;
        if (lca(i, j) == i) {
            result += dist_root[j] - dist_root[i];
        } else {
            int acc = INT_MAX;
            for (auto it : distinguished) {
                int k, distinguished_k; tie(k, distinguished_k) = it;
                if (lca(i, k) == i) {
                    chmin(acc, (dist_root[k] - dist_root[i]) + dist[distinguished_k][distinguished[ancestor[j]]] + (dist_root[j] - dist_root[ancestor[j]]));
                }
            }
            result += acc;
        }
    }

    return result;
}

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    vector<vector<pair<int, int> > > g(n);
    REP (i, m) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        -- a; -- b;
        g[a].emplace_back(b, c);
    }
    // solve
    ll result = solve(n, m, g);
    // output
    printf("%lld\n", result);
    return 0;
}