P4768 归程 最短路+Kruskal重构树

传送门：https://www.luogu.com.cn/problem/P4768

题意

在一个雨天漫步的无向联通城市，有n个点，m条边，已知小明的家是1号点。 每条边有u,v,l,a，分别代表起点，中点，长度和海拔。

给Q个询问，每次给一个v出发点和p水位线(强制在线)。 小明从点v乘车出发，当一条边的海拔小于等于p时，汽车可以通过，否则必须弃车步行。 步行不需要考虑水位线。 请输出小明在一次询问中步行的最小步行距离。

思路

首先这一题，题目很长，很难读！！！

题意转化一下，小明先乘车到一个点，由于水位线的原因不得不弃车，即先乘车后步行。

这个点就是与v联通的所有点中，与1距离最短的点。所以怎么找到这个关键点呢？

这就要请出今天的主角：Kruskal重构树

我们以海拔为边权，建立一棵边权从大到小的重构树。

假设我们找到了一棵子树的根节点u，且$val[u]>p\;\;\&\&\;\;val[fa[u]]<=p$. 那么从u出发到子树的任意节点不需要步行，所以要在很多叶子结点找距离1最短距离的点—关键点。

总结一下算法流程：

• 第一步，先跑最短路，找到1到任意点的最短距离，方便第三步更新。
• 第二步，建重构树，把问题转化成树形结构。
• 第三步，处理关键点，可树形dp，可树上倍增，找到与1距离最短的点且满足val[u]>p。

Code

##include "bits/stdc++.h"
using namespace std;

typedef long long ll;
##define endl "\n"

const int INF = 0x3f3f3f3f;

const int N = 1e6 + 10, M = 2e6 + 10;
int n, m;

/*----------最短路-------------*/
struct edge {
    int v, next, w;
}e[M];
int head[M], cnt;
struct node {
    int now, d;
    bool operator < (const node& rhs) const {
        return d > rhs.d;
    }
};
int dis[N];
bool vis[N];

void init() {
    for(int i = 1;i <= n; i++) head[i] = -1;
    cnt = 0;
}

void add(int u, int v, int w) {
    e[cnt] = {v, head[u], w};
    head[u] = cnt++;
}

void Dijkstra(int s) {
    priority_queue<node> q;
    for(int i = 1;i <= n; i++) dis[i] = INF, vis[i] = 0;
    dis[s] = 0;
    q.push({s, 0});
    while(!q.empty()) {
        node p = q.top(); q.pop();
        int u = p.now;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) q.push({v, dis[v]});
            }
        }
    }
}

/*-------------Kruskal重构树---------------*/

struct Edge {
    int u, v, w;
    bool operator < (const Edge& rhs) const {
        return w > rhs.w;
    }
}E[M];
vector<int> g[N];
int f[N], val[N], tot;
int fa[N][33], d[N];

void dfs(int u, int par) {
    d[u] = (u <= n ? dis[u] : INF);
    fa[u][0] = par;
    for(int i = 1;i <= 32; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(auto v : g[u]) {
        if(v == par) continue;
        dfs(v, u);
        d[u] = min(d[u], d[v]);
    }
    g[u].clear();
}

int get(int u, int p) {
    for(int i = 32; i >= 0; i--) {
        if(val[fa[u][i]] > p) u = fa[u][i];
    }
    return u;
}

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

void EX_Kruskal() {
    tot = n;
    for(int i = 1;i < (n << 1); i++) f[i] = i, val[i] = 0;
    sort(E + 1, E + m + 1);
    for(int i = 1;i <= m; i++) {
        int u = find(E[i].u);
        int v = find(E[i].v);
        if(u == v) continue;
        val[++tot] = E[i].w;
        f[u] = f[v] = tot;
        g[u].emplace_back(tot); g[tot].emplace_back(u);
        g[v].emplace_back(tot); g[tot].emplace_back(v);
        if(tot == (n << 1) - 1) break;
    }
    int rt = find(1);
    dfs(rt, 0);
}

void solve() {
    int _; cin >> _;
    while(_--) {
        cin >> n >> m;
        init();
        for(int i = 1;i <= m; i++) {
            int u, v, l, a; cin >> u >> v >> l >> a;
            E[i] = {u, v, a};
            add(u, v, l); add(v, u, l);
        }
        Dijkstra(1); // 先跑最短路
        EX_Kruskal(); // 在建重构树
        int lastans = 0;
        int Q, K, S; cin >> Q >> K >> S;
        while(Q--) {
            int v, p; cin >> v >> p;
            v = (v + K * lastans - 1) % n + 1;
            p = (p + K * lastans) % (S + 1);
            cout << (lastans = d[get(v, p)]) << endl;
        }
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/16/luogu-p4768/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！