kruskal 重构树
对于一张无向图, 我们在进行 kruskal 的过程中
每当合并两个联通块时
新建虚拟节点 t
对于两个联通块的根节点 fau,fav 连无向边
(fau, t),(fav, t) 其中点 t 的点权为两个联通块当前连边的边权
对于这道题
首先 dijkstra 处理所有点到 1 号点的最短路
然后按照边的海拔进行降序排序
这样做出重构树之后
显然对于点 u, 它的所有子树中的相关的边的海拔 (这里已经转化为了虚拟节点的点权) 都要大于该点的海拔
这样的话
对于询问二元组 x, h
倍增将 x 调到海拔最低且高于 h 的点处
此时 x 的子树中 dis[]的最小值即为此次询问的结果
注意: 在进行重构树时
虚拟节点的 dis[]每次可以取 min(dis[fau], dis[fav])
这样就相当于 dis[t]表示 t 的子树中 dis[]的最小值
省去了一遍 dfs
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <queue>
- #include <cstring>
- using namespace std;
- const int N = 4e5 + 10, oo = 1e9 + 7;
- struct Node {
- int u, v, len, high, nxt;
- } E[N], G[N <<2], Edge[N << 1];
- struct Node_ {
- int u, dis_;
- inline bool operator < (const Node_ a) const {return dis_> a.dis_;}
- };
- int head_1[N], head_2[N <<1], now;
- int dis[N << 1];
- bool vis[N];
- int fa[N << 1];
- int n, m;
- int High[N << 1];
- int f[N << 1][30];
- int deep[N << 1];
- #define gc getchar()
- inline int read() {
- int x = 0;
- char c = gc;
- while(c < '0' || c> '9') c = gc;
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
- return x;
- }
- int Get(int x) {return fa[x] == x ? x : fa[x] = Get(fa[x]);}
- inline bool Cmp(Node a, Node b) {return a.high> b.high;}
- void Dfs(int u, int fa) {for(int i = head_2[u]; ~ i; i = G[i].nxt) if(G[i].v != fa) f[G[i].v][0] = u, Dfs(G[i].v, u);}
- inline int Jump(int X, int H) {for(int i = 20; i>= 0; i --) if(f[X][i] && High[f[X][i]]> H) X = f[X][i];return X;}
- inline void Add_Edge(int u, int v, int Len) {Edge[++ now].v = v; Edge[now].len = Len; Edge[now].nxt = head_1[u]; head_1[u] = now;}
- inline void Add_G(int u, int v) {G[++ now].v = v; G[now].nxt = head_2[u]; head_2[u] = now;}
- inline void Pre() {for(int i = 1; i <= 20; i ++) for(int j = 1; j <= (n * 2 - 1); j ++) f[j][i] = f[f[j][i - 1]][i - 1];}
- inline void Dijkstra() {
- for(int i = 1; i <= n; i ++) dis[i] = oo;
- for(int i = 1; i <= n; i ++) vis[i] = 0;
- priority_queue <Node_> Q;
- Q.push((Node_) {1, 0});
- dis[1] = 0;
- while(!Q.empty()) {
- Node_ topp = Q.top();
- Q.pop();
- if(vis[topp.u]) continue;
- vis[topp.u] = 1;
- for(int i = head_1[topp.u]; ~ i; i = Edge[i].nxt)
- if(dis[Edge[i].v]> dis[topp.u] + Edge[i].len) {
- dis[Edge[i].v] = dis[topp.u] + Edge[i].len;
- Q.push((Node_) {Edge[i].v, dis[Edge[i].v]});
- }
- }
- }
- inline void Kruskal() {
- sort(E + 1, E + m + 1, Cmp);
- for(int i = 1; i <= (n << 1); i ++) fa[i] = i;
- for(int i = 1; i <= (n << 1); i ++) head_2[i] = -1;
- int cnt = n;
- now = 0;
- for(int i = 1; i <= m; i ++) {
- if(cnt == n * 2 - 1) break;
- int u = E[i].u, v = E[i].v, fau = Get(u), fav = Get(v);
- if(fau != fav) {
- fa[fau] = fa[fav] = ++ cnt;
- High[cnt] = E[i].high;
- dis[cnt] = min(dis[fau], dis[fav]);
- Add_G(fau, cnt), Add_G(cnt, fau), Add_G(fav, cnt), Add_G(cnt, fav);
- }
- }
- }
- int main() {
- for(int T = read(); T; T --) {
- memset(f, 0, sizeof f);
- n = read(), m = read(); now = 0;
- for(int i = 1; i <= n; i ++) head_1[i] = -1;
- for(int i = 1; i <= m; i ++) {
- int u = read(), v = read(), Len = read(), high = read();
- Add_Edge(u, v, Len), Add_Edge(v, u, Len);
- E[i] = (Node) {u, v, Len, high};
- }
- Dijkstra(), Kruskal(), Dfs(2 * n - 1, 0), Pre();
- int Q = read(), K = read(), S = read(), Lastans = 0;
- for(; Q; Q --) {
- int X = (read() + K * Lastans - 1) % n + 1, H = (read() + K * Lastans) % (S + 1);
- Lastans = dis[Jump(X, H)]; cout << Lastans << "\n";
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2732706.html