题目地址：洛谷：【P1967】货车运输 – 洛谷

题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：
输出文件名为 truck.out。
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。

输入输出样例

输入样例#1：

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出样例#1：

3
-1
3

说明

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

题解

暴力来做可以Floyd处理出两点路径上的最小边权。
我们考虑一个Kruskal算法的流程，如果是在求最大生成树，则按边权降序对边排序并加边，显然可以保证最大生成树上的路径就是最优解。因此我们把询问转换成了树上问题。
这与树链有关，所以其实我们可以选择使用树链剖分，将边权记在边较深的端点处，并线段树维护最小值。这样做的复杂度是O(n \log^2 n)的。
我们还可以用倍增思想，维护一个倍增路径上的最小权值。只需要在通常的倍增LCA算法上加一点小修改即可。这样做的复杂度是O(n \log n)，比树剖更优。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005, MAXM = 50005;

int n, m;

struct Edge {
    int to, w;
};
std::vector<Edge> gra[MAXN];

struct Edge1 {
    int u, v, w;
} edges[MAXM];

inline bool cmp(Edge1 a, Edge1 b) {
    return a.w > b.w;
}

int fa[MAXN];

inline int find(int u) {
    return fa[u] == u ? u : fa[u] = find(fa[u]);
}

inline void kruskal() {
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        int f1 = find(edges[i].u), f2 = find(edges[i].v);
        if(f1 == f2) continue;
        fa[f2] = f1;
        gra[edges[i].u].push_back(Edge {edges[i].v, edges[i].w});
        gra[edges[i].v].push_back(Edge {edges[i].u, edges[i].w});
        cnt++;
        if(cnt >= n - 1) break;
    }
}

int anc[MAXN][25], mn[MAXN][25], dep[MAXN];

inline void dfs(int u) {
    for(auto e : gra[u]) {
        int v = e.to;
        if(v == anc[u][0]) continue;
        anc[v][0] = u;
        mn[v][0] = e.w;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
}

inline void calanc() {
    for(int i = 1; i <= 20; i++) {
        for(int j = 1; j <= n; j++) {
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            mn[j][i] = std::min(mn[j][i - 1], mn[anc[j][i - 1]][i - 1]);
        }
    }
}

inline int query(int x, int y) {
    if(dep[x] > dep[y]) std::swap(x, y);
    int ans = 1e9;
    int del = dep[y] - dep[x];
    for(int i = 20; i >= 0; i--) {
        if(del & (1 << i)) {
            ans = std::min(ans, mn[y][i]);
            y = anc[y][i];
        }
    }
    if(x == y) return ans;
    for(int i = 20; i >= 0; i--) {
        if(anc[x][i] != anc[y][i]) {
            ans = std::min(ans, mn[x][i]);
            x = anc[x][i];
            ans = std::min(ans, mn[y][i]);
            y = anc[y][i];
        }
    }
    ans = std::min(ans, std::min(mn[x][0], mn[y][0]));
    return ans;
}

int q, x, y;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for(int i = 1; i <= m; i++) {
        edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
    }
    std::sort(edges + 1, edges + m + 1, cmp);
    kruskal();
    for(int i = 1; i <= n; i++) {
        if(!dep[i]) {
            dep[i] = 1;
            dfs(i);
        }
    }
    calanc();
    q = readint();
    while(q--) {
        x = readint(); y = readint();
        int f1 = find(x), f2 = find(y);
        if(f1 != f2) puts("-1");
        else printf("%d\n", query(x, y));
    }
    return 0;
}