【NOI 2018】归程（Kruskal重构树 + 倍增）

题目链接：【NOI 2018】归程

题目大意：给定一个加权无向图，$q$ 次询问，每次询问从 $v$ 点只经过海拔 $\gt w$ 的边到达的点中到 $1$ 号点的最短路为多少。强制在线。

首先，预处理出 $1$ 号点到所有点的最短路。然后，每个询问就可以变成：从 $v$ 点只经过 $\gt w$ 的边到达的点 $u$ 中 $dis[u]$ 的最小值。

这个可以用 $Kruskal$ 重构树来做。没学过的同学可以参考 这篇 Blog。
作出 $Kruskal$ 重构树后，我们处理出点 $u$ 的 $2^k$ 级父亲和他子树中到点 $1$ 的最小值。对于每个询问，我们倍增求出点 $v$ 能爬到的最高点，在输出该点的子树最小值即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int logn = 20;
const int maxn = 200005;
const int maxm = 400005;
const int maxe = 800005; 
int T, n, m, q, k, s, dist[maxn], fa[maxm], wei[maxm], f[maxm];
int tot, ter[maxe], len[maxe], nxt[maxe], lnk[maxm], p[maxm][logn];
struct edge {int u, v, w;edge() {}edge(int nu, int nv, int nw) { u = nu, v = nv, w = nw; }bool operator<(edge x) const{ return w > x.w; }
} e[maxm];
void addedge(int u, int v, int w) {ter[++tot] = v, len[tot] = w;nxt[tot] = lnk[u], lnk[u] = tot;
}
int find(int x) {return fa[x] ? fa[x] = find(fa[x]) : x;
}
void dijkstra() {priority_queue pq; pq.push(edge(1, 0, 0));memset(dist, 0x3f, sizeof(dist)); dist[1] = 0;while (!pq.empty()) {edge x = pq.top(); pq.pop();for (int i = lnk[x.u]; i; i = nxt[i]) {if (dist[ter[i]] > dist[x.u] + len[i]) {dist[ter[i]] = dist[x.u] + len[i];pq.push(edge(ter[i], 0, dist[ter[i]]));}}}
}
int kruskal() {sort(e + 1, e + m + 1);memset(fa, 0, sizeof(fa));int u, v, idx = n;for (int i = 1; i <= m; i++) {u = find(e[i].u), v = find(e[i].v);if (u == v) continue;fa[u] = fa[v] = ++idx, wei[idx] = e[i].w;addedge(idx, u, 0), addedge(idx, v, 0);}return idx;
}
void dfs(int u, int l) {for (int i = 0; (p[u][i + 1] = p[p[u][i]][i]); i++);for (int v, i = lnk[u]; i; i = nxt[i]) {if ((v = ter[i]) == l) continue;p[v][0] = u, dfs(v, u), f[u] = min(f[u], f[v]);}if (u <= n) f[u] = dist[u];
}
int main() {for (scanf("%d", &T); T--; ) {scanf("%d %d", &n, &m);int u, v, l, a;tot = 0, memset(lnk, 0, sizeof(lnk));for (int i = 1; i <= m; i++) {scanf("%d %d %d %d", &u, &v, &l, &a);addedge(u, v, l), addedge(v, u, l), e[i] = edge(u, v, a);}dijkstra();tot = 0, memset(lnk, 0, sizeof(lnk));memset(f, 0x3f, sizeof(f)), memset(p, 0, sizeof(p));dfs(kruskal(), 0);int w, lans = 0;for (scanf("%d %d %d", &q, &k, &s); q--; ) {scanf("%d %d", &v, &w);v = (v + k * lans - 1) % n + 1, w = (w + k * lans) % (s + 1);for (int i = 18; ~i; i--)  if (wei[p[v][i]] > w)   v = p[v][i];printf("%d\n", lans = f[v]);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！