题目描述

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。

0< N < 10,000，0< M < 50,000，0< Q < 30,000，0 < = z < = 100,000

输出格式

输出共有q行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。

如果货车不能到达目的地，输出-1。

---

我们可以假设一开始没有边，然后我们加了边之后某辆车的起点和终点被连通了。那么这题可以用并查集来做。

可以证明，我们往图中从大到小加入边，直到起点和终点连通时，这次加入的边就是答案。因为这条边是能让起点和终点连通的限重最大的边。这是处理一辆货车的做法。

但是本题有q辆货车，q还不小。那么我们可以干脆让原图每个连通块里面的所有点都连通了，然后找出每辆货车的路径中限重最小的边即可。然后让所有点连通的方法就是从大到小加边，并且把加入边的两个点加入一个并查集中，最后会构建出一片生成树森林，一共n-1条边。如果你对Kruskal算法熟悉的话，你会发现这就是一个求最大生成树的问题。

然后我们的下一步就是在最大生成树上求路径上边权最小值的问题。这里可以用倍增做，时间复杂度为O((N+Q)logN)，再加上之前求最大生成树的复杂度就是：

\[ O((N+Q)log_{2}N+Mlog_{2}M) \]

无解就是起点终点不在一棵生成树中。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define maxn 10001#define maxm 50001using namespace std; struct node{    int u,v,w;    bool operator<(const node &b)const{ return w>b.w; }}b[maxm];struct edge{    int to,dis,next;    edge(){}    edge(const int &_to,const int &_dis,const int &_next){ to=_to,dis=_dis,next=_next; }}e[maxn<<1];int head[maxn],k; int anc[maxn],dep[maxn];int fa[maxn][20],minedge[maxn][20],maxdep;int n,m,q; inline int read(){    register int x(0),f(1); register char c(getchar());    while(c<'0'||'9'
         
          dep[v]) swap(u,v); int ans=0x3f3f3f3f; for(register int i=maxdep;i>=0;i--) if(dep[fa[v][i]]>=dep[u]) ans=min(ans,minedge[v][i]),v=fa[v][i]; if(u==v) return ans; for(register int i=maxdep;i>=0;i--) if(fa[u][i]!=fa[v][i]) ans=min(ans,min(minedge[u][i],minedge[v][i])),u=fa[u][i],v=fa[v][i]; return min(ans,min(minedge[u][0],minedge[v][0]));} int main(){ memset(head,-1,sizeof head); n=read(),m=read(); for(register int i=1;i<=m;i++) b[i].u=read(),b[i].v=read(),b[i].w=read(); kruskal(); maxdep=(int)log(n)/log(2)+1; memset(minedge,0x3f,sizeof minedge); for(register int i=1;i<=n;i++) if(!dep[i]) dep[i]=1,dfs(i); q=read(); for(register int i=1;i<=q;i++){ int u=read(),v=read(); if(get(u)!=get(v)) puts("-1"); else printf("%d\n",getmin(u,v)); } return 0;}