题目描述

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

输入格式

第一行有两个用一个空格隔开的整数n,m，表示 A 国有n 座城市和 m 条道路。

接下来 m行每行3个整数 x, y, z，每两个整数之间用一个空格隔开，表示从 x号城市到y号城市有一条限重为 z 的道路。注意： ** x 不等于 y，两座城市之间可能有多条道路 ** 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： ** x 不等于 y ** 。

输出格式

共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出−1。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8

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

输出 #1

1
2
3

3
-1
3

解析

题目让我们求对于每个司机，最多能运多少货物，也就是在给定的两点间必经路线中求最大边权，显然我们要最大化这个边权，才能使答案更优。

注意到一些边是无论如何都不会被经过的，这些边通常较小，经过它们会劣化答案。那么一个很显然的贪心就是，排个序，依次选择最大的边加入新图，尽量不选较小的边，直到新图联通且无环，两点间有唯一的不重复经过同一条边的路径

等等……这个是最大生成树？是的。

想一想答案怎么求。
既然新图有一个性质「两点间有唯一的不重复经过同一条边的路径」，那么走一遍这条路径不就求出答案了吗！

为什么不再往上走一走？能运载的最大货物量是由这条路径决定的，往上走只可能有两种结果：上面边权比最小值大，上面边权比最小值小。第一种情况对答案没有什么贡献（因为最大值影响不了最小值），第二种情况则会劣化答案！

显然这条路径被这两个点的 LCA 分成两段，从一个点向上到 LCA 再向下到另一个点，那么在求 LCA 往上蹦的过程中求一下最小值就行了。可以倍增。

代码实现

#include
#include
#include
#include

#define FILE_IN(__fname) freopen(__fname, “r”, stdin)
#define FILE_OUT(__fname) freopen(__fname, “w”, stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 100000 + 10;
const int MAXM = MAXN * 5;
const int LOG = 21;

int n, m, q;

namespace Graph{
struct RawEdge {
int prev, next, weight;

    bool operator < (const RawEdge &that) const {
        return weight > that.weight;
    }
} redge[MAXM];

struct Edge {
    int now, next, weight;
} edge[MAXM];

int head[MAXN], cnt;

bool vis[MAXN];

void addEdge(int prev, int next, int weight) {
    edge[++cnt].now = next;
    edge[cnt].weight = weight;
    edge[cnt].next = head[prev];
    head[prev] = cnt;
}

struct UnionFind{
    int seq[MAXN];

    UnionFind() { memset(seq, 0, sizeof seq); }

    int Find(int x) {
        if (seq[x] == 0) return x;
        return seq[x] = Find(seq[x]);
    }

    bool Union(int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return false;
        seq[x] = y;
        return true;
    }
} U;

void Kruskal() {
    std::sort(redge + 1, redge + 1 + m);
    for(int i = 1; i <= m; ++i) {
        if (U.Union(redge[i].prev, redge[i].next)) {
            addEdge(redge[i].prev, redge[i].next, redge[i].weight);
            addEdge(redge[i].next, redge[i].prev, redge[i].weight);
        }
    }
}

}

namespace LCAs {
using namespace Graph;
int depth[MAXN], fa[MAXN][LOG], w[MAXN][LOG];

void Search(int root) {
    vis[root] = true;
    for(int e = head[root]; e; e = edge[e].next) {
        int now = edge[e].now;
        if (vis[now]) continue;
        depth[now] = depth[root] + 1;
        fa[now][0] = root;
        w[now][0] = edge[e].weight;
        Search(now);
    }
}

int GetAnswer(int x, int y) {
    if (U.Find(x) != U.Find(y)) return -1;
    int ans = 0x7f7f7f7f;
    if (depth[x] > depth[y]) std::swap(x,y);

    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[fa[y][i]] >= depth[x]) {
            ans = std::min(ans, w[y][i]);
            y = fa[y][i];
        }
    }

    if (x == y) return ans;

    for (int i = LOG - 1; i >= 0; --i) {
        if (fa[x][i] != fa[y][i]) {
            ans = std::min(ans, std::min(w[x][i], w[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }

    ans = std::min(ans, std::min(w[x][0], w[y][0]));
    return ans;
}

}

int main() {
using namespace LCAs;
using namespace Graph;

scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    redge[i].prev = x;
    redge[i].next = y;
    redge[i].weight = z;
}

Kruskal();

for (int i = 1; i <= n; ++i){
    if (!vis[i]) {
        depth[i] = 1;
        Search(i);
        fa[i][0] = i;
        w[i][0] = 0x7f7f7f7f;
    }
}
for (int i = 1; i <= LOG - 1; ++i) {
    for (int j = 1; j <= n; ++j) {
        fa[j][i] = fa[fa[j][i-1]][i-1];
        w[j][i] = std::min(w[j][i-1], w[fa[j][i-1]][i-1]);
    }
}

scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
    int prev, next;
    cin >> prev >> next;
    printf("%d\n", GetAnswer(prev, next));
}
return 0;

}