题目描述

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

数据范围

对于30%的数据，$ 0 < n < 1000，0 < m < 10000，0 < q< 1,000 $
对于60%的数据，$ 0 < n < 1000，0 < m < 50000，0 < q< 1,000 $
对于100%的数据，$ 0 < n < 10000，0 < m < 50000，0 < q < 30000，0 ≤ z ≤ 100,000 $

解题报告

这一题一看，发现很难。
(但是其实不难
冷静分析，发现我们可以用一个FLOYD的思想来写，但是这样只有30pts
好像还要优化...
100pts做法
我们其实只需要这个图的最大生成树即可，然后如果两个点联通，则它们连接的边就是答案，用倍增搞一下就行。

代码

#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>

const int MAXN = 10000 + 5;
const int MAXM = 50000 + 5;

struct Tree{ //存储最大生成树
    int to,next,w;
}t[MAXM];

struct Side{  //存储图（KrusKal不需要存整个图，只需要存边即可）
    int u,v,w;

    bool operator < (const Side &x) const{  //最大生成树的排序
        return w > x.w;
    }
}e[MAXM];

int N,M,log2N;
int head[MAXN],cnt;
int fa[MAXN],deep[MAXN];
bool check[MAXN];
int f[MAXN][20 + 5],w[MAXN][20 + 5]; //w[i][j]表示第i个点到向上第2^j个点的路程之间的最大权值

inline void addTree(int u,int v,int w){
    t[++cnt] = Tree{v,head[u],w};
    head[u] = cnt;
    t[++cnt] = Tree{u,head[v],w};
    head[v] = cnt;
}

inline void init(){
    for(int i = 1;i <= N;i++)
        fa[i] = i;
}

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

void Union(int x,int y){
    fa[find(x)] = find(y);
}

void KrusKal(){
    init();
    std::sort(e + 1,e + M + 1);
    int cnt = 0;
    for(int i = 1;i <= M;i++){
        if(find(e[i].u) != find(e[i].v)){
            Union(e[i].u,e[i].v);
            addTree(e[i].u,e[i].v,e[i].w);
            cnt++;
        }
        if(cnt == N - 1) break;
    }
}

void dfs(int v,int fa,int d){  //预处理每一个点
    check[v] = true;
    f[v][0] = fa;
    deep[v] = d;
    for(int i = head[v];i;i = t[i].next){
        if(!check[t[i].to]){
            w[t[i].to][0] = t[i].w;
            dfs(t[i].to,v,d + 1);
        }
    }
}

void ycl(){ //预处理LCA
    for(int i = 1;i <= N;i++)
        if(!check[i])
            dfs(i,0,1);
    for(int j = 1;j <= 20;j++){
        for(int i = 1;i <= N;i++){
            f[i][j] = f[f[i][j-1]][j-1];
            w[i][j] = std::min(w[i][j-1],w[f[i][j-1]][j-1]);
        }
    }
}

int lca(int x,int y){ //查询
    if(deep[x] < deep[y]) std::swap(x,y);
    int ret = INT_MAX;
    for(int i = 20;i >= 0;i--){
        if(deep[f[x][i]] >= deep[y]){
            ret = std::min(ret,w[x][i]);
            x = f[x][i];
        }
    }
    if(x == y) return ret;
    for(int i = 20;i >= 0;i--){
        if(f[x][i] != f[y][i]){
            ret = std::min(ret,std::min(w[x][i],w[y][i]));
            x = f[x][i];
            y = f[y][i];
        }
    }
    return ret = std::min(ret,std::min(w[x][0],w[y][0]));
}

void query(){
    int q;
    scanf("%d",&q);
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(find(x) != find(y))
            printf("-1\n");
        else
            printf("%d\n",lca(x,y));
    }
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= M;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    KrusKal();
    ycl();
    query();
    return 0;
}