洛谷4768 [NOI2018] 归程

题目大意

有一个$n$个点$m$条边的无向联通图, 每条边有两个属性:长度$d$,海拔$h$

有$q$个询问,每个询问给定两个数$v$, $p$,你要找到一个节点$u$,其中$u$要满足$v$到$u$存在一条路径使得这条路径上的边海拔全部大于$p$,求所有可能的$u$到$1$的最短路长度的最小值

分析

显然,我们发现$v$到$u$的路径一定在$u$到$v$的最大生成树上。(例:货车运输)

把边按照海拔降序排列,建出该图的$\texttt{kruskal}$重构树,则对于一个节点$s$, 若$s$的点权$val \leq p$则该子树里的所有节点都互相连通(即能开车抵达)。

我们通过$\texttt{dijkstra}$预处理出每个点到$1$的最短路$dis_i$, 并在建出$\texttt{kruskal}$重构树之后在重构树上$\texttt{dfs}$求出每个节点的子树里$dis$的最小值$mind_i$。询问时只要找到$v$最大的点权$\leq p$的祖先$x$,则$mind_x$就是本题的答案。

$x$的寻找可以使用树上倍增算法,(在满足条件的情况下)逐级往上跳

时间复杂度$O(m \log m)$

一些额外的东西

这里补充讲一下$\texttt{kruskal}$重构树是怎么建出来的:

1.像正常的$\texttt{kruskal}$重构树那样把所有边按照边权降序/升序排序

2.在合并一条边的两个端点$u, \; v$时,我们不像原来那样把$v$联通块的根节点$fv$设为$fu$,而是新建一个节点$new$并把$new$设为$fu, \; fv$的父亲,并在图中连上$(new, \; fu)$和$(new, \; fv)$两条边,此时该新点的点权就是$u$, $v$最大/小生成树路径上最小/大值

3.重复步骤$2$直到所有边都被遍历一遍

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 8e5 + 10;
const int MaxM = 1e6 + 10;

struct edge
{
int next, to, dis;
};

struct Edge
{
int u, v, ht;
};

struct node
{
int pos, dis;
bool operator<(node x) const { return dis > x.dis; }
};

edge e[MaxM];
Edge t[MaxN];
int n, m, q, k, s, cnt, num;
int head[MaxM], dep[MaxM], f[MaxM], val[MaxM], mind[MaxN];
int u[MaxN], v[MaxN], l[MaxN], a[MaxN], dis[MaxN], vis[MaxN], fa[MaxN][21];

int cmp(Edge a, Edge b) { return a.ht > b.ht; }

void link(int u, int v, int a) { ++cnt, t[cnt].u = u, t[cnt].v = v, t[cnt].ht = a; }

int getf(int x)
{
if (x != f[x])
f[x] = getf(f[x]);
return f[x];
}

void rebuild()
{
cnt = 0;
for (int i = 1; i <= m; i++)
link(u[i], v[i], a[i]);
}

int jump(int u, int k)
{
for (int i = 20; ~i; i--)
if (val[fa[u][i]] > k)
u = fa[u][i];
return u;
}

void add_edge(int u, int v, int d)
{
++cnt;
e[cnt].to = v;
e[cnt].dis = d;
e[cnt].next = head[u];
head[u] = cnt;
}

void init()
{
n = m = cnt = num = 0;
memset(f, 0, sizeof(fa));
memset(fa, 0, sizeof(fa));
memset(dep, 0, sizeof(dep));
memset(vis, 0, sizeof(vis));
memset(val, 0, sizeof(val));
memset(head, 0, sizeof(head));
memset(mind, 0x3f, sizeof(mind));
}

inline int read()
{
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}

void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1, ::fa[u][0] = fa;
for (int i = 1; i <= 20; i++)
::fa[u][i] = ::fa[::fa[u][i - 1]][i - 1];
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (v == fa)
continue;
dfs(v, u), mind[u] = std::min(mind[u], mind[v]);
}
}

void kruskal()
{
num = n, cnt = 0;
memset(head, 0, sizeof(head));
std::sort(t + 1, t + m + 1, cmp);
for (int i = 1; i <= n; i++)
f[i] = i;
for (int i = 1; i <= m; i++)
{
int fu = getf(t[i].u), fv = getf(t[i].v);
if (fu != fv)
{
val[++num] = t[i].ht;
f[num] = f[fu] = f[fv] = num;
add_edge(fu, num, 0), add_edge(num, fu, 0);
add_edge(fv, num, 0), add_edge(num, fv, 0);
}
}
dfs(num, 0);
}

void dijkstra(int u)
{
std::priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0, q.push((node){u, 0});
while (!q.empty())
{
node x = q.top();
q.pop(), u = x.pos;
if (vis[u])
continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (dis[u] + e[i].dis < dis[v])
{
dis[v] = dis[u] + e[i].dis;
if (!vis[v])
q.push((node){v, dis[v]});
}
}
}
for (int i = 1; i <= n; i++)
mind[i] = dis[i];
}

int main()
{
int T = read();
while (T--)
{
int lastans = 0;
init(), n = read(), m = read();
for (int i = 1; i <= m; i++)
{
u[i] = read(), v[i] = read(), l[i] = read(), a[i] = read();
add_edge(u[i], v[i], l[i]), add_edge(v[i], u[i], l[i]);
}
dijkstra(1), rebuild(), kruskal();
q = read(), k = read(), s = read();
while (q--)
{
int v = (read() + k * lastans - 1) % n + 1, p = (read() + k * lastans) % (s + 1);
lastans = mind[jump(v, p)], printf("%d\n", lastans);
}
}
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×