Problem#
Truck Transportation#
Country A has $n$ cities, numbered from $1$ to $n$, and there are $m$ bidirectional roads between the cities. Each road has a weight limit for vehicles, referred to as the weight limit.
Now there are $q$ trucks transporting goods, and the drivers want to know the maximum weight of goods each truck can carry without exceeding the vehicle weight limit.
Input Format#
The first line contains two integers $n,m$ separated by a space, indicating that country A has $n$ cities and $m$ roads.
The next $m$ lines each contain three integers $x, y, z$, with a space between each pair of integers, indicating that there is a road from city $x$ to city $y$ with a weight limit of $z$.
Note: $x \neq y$, and there may be multiple roads between two cities.
The next line contains an integer $q$, indicating that there are $q$ trucks that need to transport goods.
The next $q$ lines each contain two integers $x,y$, separated by a space, indicating that a truck needs to transport goods from city $x$ to city $y$, ensuring that $x \neq y$.
For $100%$ of the data, $1 \le n < 10^4$, $1 \le m < 5\times 10^4$, $1 \le q< 3\times 10^4 $, $0 \le z \le 10^5$.
Solution#
Since we need to maximize the minimum value along the path, ~binary search (of course it can be done, but I won't QAQ)~ we can find the maximum spanning tree, and then for each query, we can use LCA to find the minimum value along the path.
The specific implementation is similar to LCA.
Issues#
-
Build bidirectional edges.
-
Union-Find
fa[/*!!!*/x_fa] = y; -
Line 125, changing min to anc.
Code#
#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();
// for(int i = 1;i <= n;i++)
// {
// cout << "qwq "<<path_min[i][2] << endl;
// }
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;
}
}