题目描述
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; }
