题目描述
A国有n座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入输出格式
输入格式:
第一行有两个用一个空格隔开的整数n,m,表示 A 国有 n 座城市和 m 条道路。
接下来 mm行每行 3 3个整数 x, y, z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路 。
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 。
输出格式:
共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出-1。
题意:一条路径的值为该路径的中所有边中的最小值,求A->B的所以路径中最大值
思路:kruskal重构树 + LCA
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int head[maxn], top[maxn], father[maxn];
int son[maxn], size[maxn], depth[maxn];
int fa[maxn], val[maxn], L[maxn], R[maxn], vis[maxn];
int n, m, q, u, v, tot, cnt, Index;
struct Node {
int u, v, w;
bool operator < (const Node &x) const {
return w > x.w; //按最大值排序
}
}a[maxn];
struct Edge {
int u, v, next;
}edge[maxn];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void init() {
memset(head, -1, sizeof(head));
tot = 1;
}
void add(int u, int v) {
edge[++tot].u = u; edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs1(int u, int fa) {
size[u] = 1;
son[u] = 0;
vis[u] = 1;
father[u] = fa;
depth[u] = depth[fa] + 1;
int maxson = -1;
for (int i = head[u]; i != -1; i = edge[i].next) {
int to = edge[i].v;
if (to == fa) {
continue;
}
dfs1(to, u);
size[u] += size[to];
if (size[to] > maxson) {
maxson = size[to];
son[u] = to;
}
}
}
void dfs2(int u, int topf) {
top[u] = topf;
L[u] = R[u] = ++Index;
if (son[u]) {
dfs2(son[u], topf);
}
for (int i = head[u]; i != -1; i = edge[i].next) {
int to = edge[i].v;
if (top[to]) {
continue;
}
dfs2(to, to);
}
R[u] = Index;
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (depth[top[x]] < depth[top[y]]) {
swap(x, y);
}
x = father[top[x]];
}
if (depth[x] > depth[y]) {
return y;
}
return x;
}
void kruskal() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
sort(a + 1, a + m + 1);
for (int i = 1; i <= m; i++) {
int fu = find(a[i].u);
int fv = find(a[i].v);
if (fu != fv) {
++cnt;
fa[cnt] = fa[fu] = fa[fv] = cnt;
val[cnt] = a[i].w;
add(cnt, fu); add(fu, cnt);
add(cnt, fv); add(fv, cnt);
}
}
for(int i=1;i<=cnt;++i) {
if(!vis[i]){
int f=find(i);
dfs1(f,0); dfs2(f,f);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
init();
cin >> n >> m; cnt = n;
for (int i = 1; i <= m; i++) {
cin >> a[i].u >> a[i].v >> a[i].w;
}
kruskal();
cin >> q;
while (q--) {
cin >> u >> v;
if (find(u) != find(v)) {
cout << "-1" << endl;
continue;
}
cout << val[LCA(u, v)] << endl;
}
return 0;
}