题意描述

$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$ 。

Input & Output ‘s examples

Input ‘s eg

markdown

Output ‘s eg

markdown

3
-1
3

数据范围和约定

对于 $30 %$ 的数据， $0 < n < 1, 000, 0 < m < 10, 000, 0 < q < 1, 0000$

对于 $60 %$ 的数据， $0 < n < 1, 000, 0 < m < 50, 000, 0 < q < 1, 0000$

对于 $100 %$ 的数据， $0 < n < 10, 000, 0 < m < 50, 000, 0 < q < 30, 000, 0 \leq z \leq 100, 0000$

分析

最大生成树 + 倍增 $L C A$

首先，我们很容易看出有一些边权很小的边（即限重很小的边）是永远不会被走过的。因此，我们可以求一颗最大生成树。

之后我们需要寻找给出两点之间的路径。又因为在生成树上，两点间的路径唯一。so…… 我们只需找到这条路径上边权最大的边即可。

我们可以使用最近公共祖先来实现这个过程：首先对最大生成树的每一个节点进行遍历，求出深度等相关信息，之后利用他们进行倍增。

Code[Accepted]

cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

int n , m , s;

struct Edge1{
    int from , to;
    ll dis;
}EDGE[N << 1];

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

struct Edge{
    int to;
    int last;
    ll dis;
}edge[N << 1];

int head[N << 1];
int edge_num;

I void add_edge(int from , int to , ll dis){
    edge[++ edge_num] = Edge{to , head[from] , dis};
    head[from] = edge_num;
}

int pre[N];

int find(int root){
    if(pre[root] == root){
        return root;
    }
   else{
       return pre[root] = find(pre[root]);
   } 
}

void merge(int a , int b){
    pre[find(a)] = find(b);
}

void Kruskal(){
    for(int i = 1; i <= n; i ++){
        pre[i] = i;
    }
    sort(EDGE + 1 , EDGE + 1 + m , cmp);
    for(int i = 1; i <= m; i ++){
        if(find(EDGE[i].from) != find(EDGE[i].to)){
            merge(EDGE[i].from , EDGE[i].to);
            add_edge(EDGE[i].from , EDGE[i].to , EDGE[i].dis);
            add_edge(EDGE[i].to , EDGE[i].from , EDGE[i].dis);
        }
    }
}

int fa[N][22];
int dep[N];
ll val[N][22];
bool vis[N];

void search(int x){
    vis[x] = true;
    for(int i = head[x] ; i ; i = edge[i].last){
        int to = edge[i].to;
        if(vis[to]){
            continue;
        }
        fa[to][0] = x;
        dep[to] = dep[x] + 1;
        val[to][0] = edge[i].dis;
        search(to);
    }
    return ;
}

int LCA(int x , int y){
    if(find(x) != find(y)){
        return -1;
    }
    ll ans = 2147483647;
    if(dep[x] > dep[y]){
        swap(x , y);
    }
    for(int i = 20; i >= 0; i --){
        if(dep[fa[y][i]] >= dep[x]){
            ans = min(ans , val[y][i]);   
            y = fa[y][i]; 
        }
    }
    if(x == y){
        return ans;
    }
    for(int i = 20; i >= 0; i --){
        if(fa[x][i] != fa[y][i]){
        	ans = min(ans , min(val[x][i] , val[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return min(ans, min(val[x][0], val[y][0]));
}

int main(){

    int u , v , d;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> u >> v >> d;
        EDGE[i].from = u;
        EDGE[i].to = v;
        EDGE[i].dis = d;
    }
    Kruskal();
    for(int i = 1; i <= n; i ++){
        if(!vis[i]){
            dep[i] = 1;
            search(i);
            fa[i][0] = i;
            val[i][0] = 0x3f3f3f3f;
        }
    }
    for(int j = 1; j <= log2(n); j ++){
        for(int i = 1; i <= n; i ++){
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            val[i][j] = min(val[i][j - 1] , val[fa[i][j - 1]][j - 1]);
        }
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i ++){
        cin >> u >> v;
        cout << LCA(u , v) << "\n";
    }

    return 0;
}