[NOIP2013 提高组] 货车运输

题目背景

NOIP2013 提高组 D1T3

题目描述

A 国有 $n$ 座城市，编号从 $1$ 到 $n$，城市之间有 $m$ 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 $q$ 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式

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

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

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

接下来 $q$ 行，每行两个整数 $x,y$，之间用一个空格隔开，表示一辆货车需要从 $x$ 城市运输货物到 $y$ 城市，保证 $x \neq y$

输出格式

共有 $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

实现

​ 最初的想法是tarjan缩点，去环后倍增求最小值，仔细思考后发现是完全没有道理的，无法在多条路线里面找到最优的路线，所以转变为用生成树重构图确定唯一的路线后再去倍增求最小值

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf32 = 1e9 + 7;
constexpr int inf64 = 1e9 + 7;
const int N=2e5+10;
typedef pair<int,int> PII;
int n,m;
struct tree{
    int u,v,w;
    bool operator< (const tree &t) const{
        return w>t.w;
    }
}edge[N];
vector<PII>e[N];
int p[N],ans,cnt;
int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int per[N][32];
int val[N][32];
int dep[N];
int st[N];
void dfs(int u,int f){
    dep[u]=dep[f]+1;
    st[u]=1;
    for(auto [v,w]:e[u]){
        if(v==f) continue;
        per[v][0]=u;
        val[v][0]=w;
        dfs(v,u);
    }
}
void kruskal(){
    sort(edge+1,edge+1+m);          //根据边权排序，由大到小枚举
    for(int i=1;i<=m;i++){
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x!=y){                   //若父节点与子节点在同一集合则不可连边，否则出现环
            e[edge[i].u].push_back({edge[i].v,edge[i].w});
            e[edge[i].v].push_back({edge[i].u,edge[i].w});
            p[x]=y;
            ans+=edge[i].w;
            cnt++;                  //重构后的树点的个数加一
        }
    }
}
int query(int u,int v){             //倍增lca求路径最小值
    int ans=1e9;
    if(dep[u]>dep[v]) swap(u,v);
    int d=dep[v]-dep[u];
    for(int j=20;j>=0;j--){
        if(d&(1<<j)){
            ans=min(ans,val[v][j]);
            v=per[v][j];
        }
    }
    if(u==v){
        return ans;
    }
    for(int j=20;j>=0;j--){
        if(per[u][j]!=per[v][j]){
            ans=min(ans,min(val[u][j],val[v][j]));
            u=per[u][j];
            v=per[v][j];
        }
    }
    ans=min(ans,min(val[u][0],val[v][0]));
    return ans;
}
void solve(){
    //int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edge[i]={u,v,w};
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    kruskal();
    for(int i=1;i<=n;i++){
        if(!st[i]) dfs(i,0);
    }
    //dfs(1,0);
    for(int j=1;j<32;j++){          //构建st表
        for(int i=1;i<=n;i++){
            per[i][j]=per[per[i][j-1]][j-1];
            val[i][j]=min(val[i][j-1],val[per[i][j-1]][j-1]);
        }
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int u,v;
        cin>>u>>v;
        if(find(u)!=find(v)){
            cout<<-1<<endl;
        }
        else{
            cout<<query(u,v)<<endl;
        }
    }
}    
signed main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}