题目
货车运输
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 $ n,m$，表示 A 国有 $ n$ 座城市和 m 条道路。
接下来 m 行每行三个整数 x,y,z，每两个整数之间用一个空格隔开，表示从 $x $ 号城市到 $ y $ 号城市有一条限重为 z 的道路。
注意： x=y，两座城市之间可能有多条道路 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x,y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，保证 x=y
对于 100% 的数据，1≤n<104，1≤m<5×104，$1 \le q< 3\times 10^4 $，0≤z≤105。
题解
由于要求路径上的最小值最大，所以 二分（当然可以，但我不会QAQ） 求出最大生成树来，然后对于每次询问的两点lca查询路径上的最小值即可
具体实现和lca差不多
问题
1.建双向边
2.并查集fa[/*!!!*/x_fa] = y;
3.125行取min写成了anc
代码
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
174
175
176
177
178
179
180
181
182
183
184
185
186
| #include<bits/stdc++.h>
using namespace std;
int read()
{
int f = 1, x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return f * x;
}
const int N = 1e4 + 10, M = 1e5 + 100;
struct U
{
int x, y, z;
bool operator < (const U o) const
{
return z > o.z;
}
}u[M >> 1]; int cnt = 1;
int fa[N], n, m;
int anc[N][20], path_min[N][20], depth[N];
int getfa(int u)
{
if(fa[u] == u) return u;
return fa[u] = getfa(fa[u]);
}
void merge(int x, int y)
{
int x_fa = getfa(x), y_fa = getfa(y);
fa[x_fa] = y;
}
int head[N], nxt[M], to[M], edge[M], tot = 1;
void add(int x, int y, int z)
{
to[++tot] = y;
edge[tot] = z;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int u, int fa)
{
depth[u] = depth[fa] + 1;
anc[u][0] = fa;
for(int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if(v == fa) continue;
path_min[v][0] = edge[i];
dfs(v, u);
}
}
void lca_init()
{
for(int j = 1;j < 20;j++)
{
for(int i = 1;i <= n;i++)
{
anc[i][j] = anc[anc[i][j - 1]][j - 1];
path_min[i][j] = min(path_min[i][j - 1], path_min[anc[i][j - 1]][j - 1]);
}
}
}
int lca_query_anc(int x, int y)
{
if(depth[x] < depth[y])
swap(x, y);
for(int i = 19;i >= 0;i--)
{
if(depth[anc[x][i]] >= depth[y])
x = anc[x][i];
}
if(x == y) return x;
for(int i = 19;i >= 0;i--)
{
if(anc[x][i] != anc[y][i])
x = anc[x][i], y = anc[y][i];
}
return anc[x][0];
}
int lca_query_min(int x, int y)
{
int ans = 0x3f3f3f3f;
if(depth[x] < depth[y])
swap(x, y);
for(int i = 19;i >= 0;i--)
{
if(depth[anc[x][i]] >= depth[y])
{
ans = min(ans, path_min[x][i]); x = anc[x][i];
}
}
if(x == y) return ans;
for(int i = 19;i >= 0;i--)
{
if(anc[x][i] != anc[y][i])
{
ans = min(ans, path_min[x][i]), ans = min(ans, path_min[y][i]);
x = anc[x][i], y = anc[y][i];
}
}
return min(ans, min(path_min[x][0], path_min[y][0]));
}
int main()
{
n = read(), m = read();
for(int i = 1;i <= n;i++)
{
fa[i] = i;
}
int x, y, z;
for(int i = 1;i <= m;i++)
{
x = read(), y = read(), z = read();
u[cnt].x = x;
u[cnt].y = y, u[cnt].z = z;
++cnt;
}
sort(u + 1, u + 1 + m);
for(int i = 1;i <= m;i++)
{
int x_fa = getfa(u[i].x), y_fa = getfa(u[i].y);
if(x_fa != y_fa)
{
merge(u[i].x, u[i].y);
add(u[i].x, u[i].y, u[i].z);
add(u[i].y, u[i].x, u[i].z);
}
}
for(int i = 1;i <= n;i++)
{
if(fa[i] == i)
{
dfs(i, 0);
}
}
lca_init();
int q;
q = read();
while(q--)
{
x = read(), y = read();
int x_fa = getfa(x), y_fa = getfa(y);
if(x_fa != y_fa)
{
printf("-1\n");
continue;
}
cout << lca_query_min(x, y) << endl;
}
}
|