P2934 [USACO09JAN] Safe Travel G

happybob · 2024-02-25 19:43:34 · 题解

题意：P2934 [USACO09JAN] Safe Travel G。

简要题意：n 个点 m 条边的简单无向连通图，对于 i \in [2,n]，求出如果删掉 1 到 i 最短路的最后一条边，新的最短路长度。保证 1 到任意一个点最短路唯一。

解法：

首先介绍最短路树。

考虑求出从 1 到每个点的最短路，以及每个点的前驱，也就是最短路上倒数第二个点，记为 fa_u（在本题中是唯一的，一般图不一定唯一）。然后考虑一个图，有 n-1 条边，每条边是 fa_u \leftrightarrow u(u \in [2,n])。

这个图有 n 个点，n-1 条边。事实上可以发现，无论最短路是否唯一，只要无负环，这个图必然连通，于是这个图必然是一棵树。

考虑将这棵树视为以 1 为根的有向树。有什么性质？首先，比较显然，由于最短路有最优子结构，1 到每个点 i 的最短路，就是树上 1 \rightarrow i 的简单路径。其次，对于树上两个点 u,v，u 为 v 的祖先，那么 u \rightarrow v 的简单路径也是原图上 u \rightarrow v 的最短路。

现在考虑原题。相当于我要删掉每条边，设这条边的两个端点较深的是 u，我现在要求 1 \rightarrow u 的最短路。那么必然是，从 1 沿着树走到某个点，然后通过一条非树边，跳到 u 的子树内，然后走回 u。我们可以证明只会经过一条非树边。

证明：

假如我们走进了 u 子树，那肯定不会在通过任何非树边走，因为这不优，与性质 2 矛盾。

其次，假如在进入 u 子树前走了两次非树边，容易注意到这和性质 1，即 1 \rightarrow i 最短路是树上路径矛盾。

证毕。

那只要考虑枚举每条非树边 (u,v)。我们知道 u,v 需要走 u,v 这条边的必然是从非子树内跨入子树内，于是那些要被更新答案的点必然在 u 到 v 路径上，且不是 \operatorname{LCA}(u,v)。然后，考虑这些点中每一个，记为 k。容易观察到，这时 k 的答案其实是 dis_u+dis_v+w-dis_k。dis_i 是 1 \rightarrow i 最短路长度，w 是 (u,v) 这条边的权值。而 dis_k 与 (u,v) 无关，可以单独处理。剩余的 dis_u+dis_v+w，可以从小到大排序，然后就变成了这样的问题；一棵树，每次给两个点和一个权值，然后将链上没有覆盖过的点覆盖为这个权值。当然你可以树剖做到 2\log，不过我们考虑并查集！每个点维护 f_u 表示 u 的祖先（不包含 u），最深的没被覆盖过的点，没有记为 0。然后每次暴力跳并查集即可。每个点只会被覆盖 1 次。如果使用 O(1) LCA，就可以做到 O(n \alpha(n))。然而我写的还是 O(n \log n) 的。

特别注意，\operatorname{LCA}(u,v) 不能被覆盖答案。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <cassert>
#include <map>
using namespace std;

const int N = 2e5 + 5;

int n, m;
vector<pair<int, int>> G[N];
vector<int> NG[N];
int pre[N];
int dis[N];
bool vis[N];

struct Node
{
    int u, d;
    Node(int u, int d) :u(u), d(d) {}
    Node() = default;
    bool operator<(const Node& g) const
    {
        return d > g.d;
    }
};

int fa[N][20];
int dep[N];

void dfs(int u, int f)
{
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    for (auto& j : NG[u]) if (j ^ f) dfs(j, u);
}

struct Edge
{
    int u, v, w;
    Edge() = default;
    Edge(int u, int v, int w) :u(u), v(v), w(w) {}
};

bool chk[N];

class Dsu
{
public:
    int f[N];
    void Init()
    {
        for (int i = 1; i <= n; i++) f[i] = fa[i][0];
    }
    int find(int u)
    {
        if (u == 0) return u;
        if (!chk[f[u]]) return f[u];
        return f[u] = find(f[u]);
    }
}dsu;

int ans[N];

int u[N], v[N], w[N];

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    memset(dis, 0x3f, sizeof dis);
    memset(ans, 0x3f, sizeof ans);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        ::u[i] = u, ::v[i] = v, ::w[i] = w;
        G[u].emplace_back(make_pair(v, w));
        G[v].emplace_back(make_pair(u, w));
    }
    auto dijkstra = [&](int st)->void
        {
            priority_queue<Node> q;
            dis[st] = 0;
            q.push(Node(st, 0));
            while (q.size())
            {
                auto [u, d] = q.top();
                q.pop();
                if (vis[u]) continue;
                vis[u] = 1;
                for (auto& [j, w] : G[u])
                {
                    if (dis[j] > dis[u] + w)
                    {
                        pre[j] = u;
                        dis[j] = dis[u] + w;
                        q.push(Node(j, dis[j]));
                    }
                }
            }
        };
    dijkstra(1);
    for (int i = 2; i <= n; i++) NG[pre[i]].emplace_back(i);
    dfs(1, 0);
    auto Init = [&]()->void
        {
            for (int j = 1; j <= 19; j++)
            {
                for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
            }
        };
    Init();
    auto LCA = [&](int u, int v)->int
        {
            if (u == v) return u;
            if (dep[u] < dep[v]) swap(u, v);
            int c = 0, k = dep[u] - dep[v];
            while (k)
            {
                if (k & 1) u = fa[u][c];
                c++;
                k >>= 1;
            }
            if (u == v) return u;
            for (int i = 19; i >= 0; i--) if (fa[u][i] ^ fa[v][i]) u = fa[u][i], v = fa[v][i];
            return fa[u][0];
        };
    vector<Edge> ve;
    for (int i = 1; i <= m; i++)
    {
        int u = ::u[i], v = ::v[i], w = ::w[i];
        int nval = dis[u] + dis[v] + w;
        ve.emplace_back(Edge(u, v, nval));
    }
    sort(ve.begin(), ve.end(), [&](const auto& h, const auto& x) {return h.w < x.w; });
    dsu.Init();
    for (auto& [u, v, w] : ve)
    {
        if (pre[u] == v || pre[v] == u) continue;
        if (dep[u] > dep[v]) swap(u, v);
        int k = LCA(u, v);
        if (k != u)
        {
            if (!chk[u])
            {
                chk[u] = 1;
                ans[u] = w;
            }
        }
        if (k != v && !chk[v]) chk[v] = 1, ans[v] = w;
        int j = u;
        while (true)
        {
            int p = dsu.find(j);
            if (!p || dep[p] <= dep[k]) break;
            chk[p] = 1, ans[p] = w;
        }
        j = v;
        while (true)
        {
            int p = dsu.find(j);
            if (!p || dep[p] <= dep[k]) break;
            chk[p] = 1, ans[p] = w;
        }
    }
    for (int i = 2; i <= n; i++)
    {
        if (ans[i] == ans[0]) cout << "-1\n";
        else cout << ans[i] - dis[i] << "\n";
    }
    return 0;
}