ゆらのふなびと

競プロ, Python, C++

JAG夏合宿Day4 F. Find the Length

本番マヨバタが話していたことを思い出しつつAC。

問題

$n$ 頂点の連結な重み付き無向グラフが与えられる。各頂点 $v$ について、$v$ を含む単純閉路長の最小値を求めよ。

制約

$1 \leq n \leq 300$

各辺の重みは隣接行列形式で与えられる

辺の重み: $1 \leq a_{ij} \leq 10^6$

解法

abc022.contest.atcoder.jp

pakapa104.hatenablog.com

↑これを思い出すと、頂点 $v$ を含む最小閉路の長さは、頂点 $v$ に隣接するすべての辺 $e_{vu}$ について、「グラフから $e_{vu}$ を取り除いたときの $vu$ 間の最短経路長 + $e_{vu}$ の長さ」で求められるのでした。しかしこのアルゴリズムの計算量は $O(VElogV)$ *1 なので、これを全頂点について行うと $O(V^2ElogV) = O(V^4logV)$ となりTLEです。

「辺を1本を削除して毎回ダイクストラ」が重いので、逆に「ベースとなる部分を先に作っておき、そこに辺を追加することで閉路をつくる」と考えます。この「ベースとなる部分」が最短経路木です。最短経路木を作っておくと、これは全域木なので木に含まれない辺を1本追加することで閉路を作れます。最短経路木自体の作り方は、ダイクストラならある頂点までの最短距離が更新されるとき、その頂点に入る辺が決まるのでそれを更新していくとできます(詳しくはコードを参照)。

$v$ を含む閉路は、$v$ を根とする最短経路木において $v$ をLCAとするような頂点対 $(i, j)$ を調べればよいです。ただし $(i, j)$ 間に辺が存在しないときは閉路を作れないので除きます。また、$i, j$ の一方が $v$ かつ他方が $v$ の直接の子である場合には、同じ辺を2度採用してしまうのでこれもアウトです。

計算量は $O(V(ElogV + V^2)) = O(V^3logV)$ です。

細々としたこと

  • typedefはusingにするとtemplateが使える(Graphが行先の頂点しか持たない場合とコストつきの辺を持つ場合の両方に対応させた)

  • LCAの根を最短経路木と同じにしてやる(それはそう)

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto&& x : v){cout << x << " ";} cout << endl
#define printVV(vv) for(auto&& v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto&& p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
const int inf = 1e9;
const int mod = 1e9 + 7;
// typedef vector<vector<int>> Graph;

template<class T>
using Graph = vector<vector<T>>;

struct edge {
    int to, cost;
    edge(){}
    edge(int _to, int _cost) : to(_to), cost(_cost) {}
};

vi d;   // d[i] = cost from s to i

Graph<edge> shortestPathTree(const Graph<edge>& G, int s) {
    int n = G.size();
    priority_queue<Pii, vector<Pii>, greater<Pii>> pq;   // cost, vertex
    d.clear();
    d.resize(n, inf);
    d[s] = 0;
    pq.push(make_pair(0, s));
    vi pre_v(n);
    vi pre_cost(n);

    while (!pq.empty()) {
        auto p = pq.top(); pq.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (const auto& e : G[v]) {
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                pq.push(make_pair(d[e.to], e.to));
                pre_v[e.to] = v;
                pre_cost[e.to] = e.cost;
            }
        }
    }

    Graph<edge> T(n);
    rep(i, n) {
        if (i == s) continue;
        T[pre_v[i]].emplace_back(i, pre_cost[i]);
    }
    return T;
}

class LCA {
private:
    static const int MAX_LOG = 20;
    const int n;
    const int root;
    Graph<int> G;
    vvi par;
    vi depth;
    // 各頂点の深さと、1つ前の親を求める
    void dfs(int v, int p, int d) {
        par[0][v] = p;
        depth[v] = d;
        for (auto nxt : G[v]) {
            if (nxt != p) {
                dfs(nxt, v, d + 1);
            }
        }
    }
public:
    LCA(int _n, int _root) : n(_n), root(_root), G(_n), par(MAX_LOG, vi(_n)), depth(_n) {}
    // undirected
    void addEdge(int a, int b) {
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
    // 各頂点の2^k番目の親を求めておく
    void init() {
        // rootを根として1つ目の親を求める
        dfs(root, -1, 0);
        // 2^i番目の親を求める
        rep(i, MAX_LOG - 1) {
            rep(j, n) {
                if (par[i][j] == -1) {
                    par[i + 1][j] = -1;
                } else {
                    par[i + 1][j] = par[i][par[i][j]];
                }
            }
        }
    }
    int lca(int a, int b) {
        // まずaとbの深さを揃える
        if (depth[a] > depth[b]) {
            swap(a, b);
        }
        rep(i, MAX_LOG) {
            if ((depth[b] - depth[a]) >> i & 1) {
                b = par[i][b];
            }
        }
        if (a == b) return a;
        // ぶつかる直前までa, bを上げる
        rrep(i, MAX_LOG) {
            if (par[i][a] != par[i][b]) {
                a = par[i][a];
                b = par[i][b];
            }
        }
        // aとbの1つ前の親は一致している
        return par[0][a];
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    cin >> n;
    Graph<edge> G(n);
    vvi A(n, vi(n));
    rep(i, n) {
        rep(j, n) {
            cin >> A[i][j];
            if (A[i][j] > 0) {
                G[i].emplace_back(j, A[i][j]);
                G[j].emplace_back(i, A[i][j]);
            }
        }
    }

    rep(v, n) {
        Graph<edge> T = shortestPathTree(G, v);
        vector<bool> isChildOfRoot(n, false);
        for (auto e : T[v]) {
            isChildOfRoot[e.to] = true;
        }

        LCA lca(n, v);
        rep(i, n) {
            for (auto e : T[i]) {
                lca.addEdge(i, e.to);
            }
        }
        lca.init();

        int ans = inf;
        rep(i, n) {
            rep2(j, i + 1, n) {
                if (A[i][j] > 0 && lca.lca(i, j) == v && !(i == v && isChildOfRoot[j]) && !(j == v && isChildOfRoot[i])) {
                    ans = min(ans, d[i] + d[j] + A[i][j]);
                }
            }
        }
        if (ans == inf) ans = -1;
        cout << ans << endl;
    }

}

*1:頂点 $v$ に隣接する辺の本数は $O(V)$, それらについて毎回ダイクストラ