[NOIP2013] 货车运输

题目链接

洛谷

LOJ

题目分析

如果两座城市之间有多条路径可以相互到达,我们会选择路径中最小值最大的,其他较次的方案会被抛弃,最后得到的就是这张图的最大生成树。

得到最大生成树之后,对于任意一次查询,我们找一个点让这两个点都能到达,路径上的最小值即为答案。不难想到可以用 LCA 来实现,本题似乎不用倍增也能跑得很快,但我还是用的倍增。

对于求最大生成树,我用了 Prim 来实现。本题城市群之间可能不联通,在求 LCA 之前的 dfs 可以先进行染色,如果询问中的两座城市颜色不一样那就不联通。

代码实现

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000010;

struct Node {
int id, dis, from;
};

struct Edge {
int nxt;
int to;
int w;
bool vis;
} edge[MAXN * 2];
priority_queue<Node> q;
int head[MAXN], cnt;
int N, M, Q;
int minn[MAXN][21];//minn[i][j]记录从i往上跳2^j个点的最大限重
int fa[MAXN][21], dep[MAXN];

namespace Prim
{
int vis[MAXN];
}// namespace Prim

namespace LCA
{
int col[MAXN];
int cnt;
}// namespace LCA

bool operator<(const Node& a, const Node& b)
{
return a.dis < b.dis;
}

void link(int u, int v, int w)
{
edge[++cnt].nxt = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt;
}

void prim()
{
for (int i = 1; i <= N; i++) {
if (Prim::vis[i]) continue;
q.push(Node{i, 0, 0});
while (!q.empty()) {
Node u = q.top();
q.pop();
if (Prim::vis[u.id]) continue;
Prim::vis[u.id] = 1;

edge[u.from].vis = 1; //记录该边属于最大生成树
if (u.from & 1) {
edge[u.from + 1].vis = 1;
} else {
edge[u.from - 1].vis = 1;
} //双向边

for (int i = head[u.id]; i; i = edge[i].nxt) {
int to = edge[i].to;
int w = edge[i].w;
int from = i;
if (Prim::vis[to]) continue;
q.push(Node{to, w, from});
}
}
}
}

void dfs(int x, int father, int w, int col)
{
if (LCA::col[x]) return;
LCA::col[x] = col;//染色
fa[x][0] = father;
minn[x][0] = w;//到父节点的minn就是到父节点的边的长度
dep[x] = dep[father] + 1;
for (int i = 1; (1 << i) <= dep[x]; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
minn[x][i] = min(minn[x][i - 1], minn[fa[x][i - 1]][i - 1]);//倍增求最小边长
}
for (int i = head[x]; i; i = edge[i].nxt) {
int to = edge[i].to;
int cw = edge[i].w;
if (to == father) continue;
if (!edge[i].vis) continue;//必须是最大生成树上有的边
dfs(to, x, cw, col);
}
}

int getlca(int a, int b)
{
if (LCA::col[a] != LCA::col[b]) return -1;
int ans = 0x7fffffff;
if (dep[a] < dep[b]) swap(a, b);
for (int i = 20; i >= 0; i--) {
if (dep[a] - (1 << i) >= dep[b]) {
ans = min(ans, minn[a][i]);
a = fa[a][i];
}
}
if (a == b) return ans;
for (int i = 20; i >= 0; i--) {
if (fa[a][i] == fa[b][i]) continue;

ans = min(ans, min(minn[a][i], minn[b][i]));
a = fa[a][i], b = fa[b][i];
}
return min(ans, min(minn[a][0], minn[b][0]));
}

int main()
{
cin >> N >> M;
for (int i = 1; i <= M; i++) {
int u, v, w;
cin >> u >> v >> w;
link(u, v, w);
link(v, u, w);
}
//使用prim求最大生成树
prim();

cin >> Q;
//倍增LCA
memset(minn, 0x3f, sizeof(minn));
for (int i = 1; i <= N; i++) {
dfs(i, 0, 0, ++LCA::cnt);
}
for (int i = 1; i <= Q; i++) {
int a, b;
cin >> a >> b;
cout << getlca(a, b) << endl;
}

return 0;
}

[NOIP2013] 货车运输
http://xiao-h.com/2023/09/10/NOIP2013-货车运输/
作者
小H
发布于
2023年9月10日
许可协议