题面
Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
Input
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
Output
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
Sample Output
3
-1
3
Hint
对于 30%的数据，0 ＜ n ＜1,000，0 ＜ m ＜ 10,000，0 ＜ q ＜ 1,000；
对于 100%的数据，0 ＜ n ＜ 10,000，0 ＜ m ＜ 50,000，0 ＜ q ＜ 30,000，0 ≤ z ≤ 100,000。
题解
这道题方法很多很多，听说可以运用网络流、树链剖分等等等方法。
我用的方法适合我这种小蒟蒻
我们看看题目，要求的是给定的两对点之间的所有路径中，路径中最短的边的最大值。
这一类题目很容易想到构造 最大/最小生成树
我们可以证明这条路径必定在最大生成树上。
假设最大生成树上两点之间的路径的最小值为x
若存在另外一条路径，使得这两点之间的路径的最小值为x'
x'>x
那么，根据最小生成树建树的原理，x'这条路径必定会在x之间建出，
因此不可能存在不在最大生成树上的边可以使得答案更大。
那么，求出最大生成树之后，直接使用倍增LCA求解即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 11000
#define MAXL 51000
#define INF 20000000
inline int read()
{
register int x=0,t=1;
register char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
int f[MAX],dep[MAX];
int minl[MAX][15],p[MAX][51];
int n,m,Q,u,v,w;
struct Line
{
int u,v,w;//从u到v，权值w
}e[MAXL];
struct Edge
{
int v,next,w;
}E[MAXL];
int h[MAX],cnt=1,tot=1;
inline void Add(int u,int v,int w)//建边
{
E[tot]=(Edge){v,h[u],w};
h[u]=tot++;
}
inline bool operator <(Line a,Line b)//需要求最大生成树
{
return a.w>b.w;
}
int getf(int u)//并查集
{
return f[u]==u?u:f[u]=getf(f[u]);
}
void Build(int u,int ff)//建树
{
for(int i=h[u];i;i=E[i].next)
{
int v=E[i].v;
if(v!=ff)
{
dep[v]=dep[u]+1;
p[v][0]=u;
minl[v][0]=E[i].w;
Build(v,u);
}
}
}
void Prepare()//LCA的预处理
{
for(int j=1;(1<<j)<=n;++j)
{
for(int i=1;i<=n;++i)
{
p[i][j]=p[p[i][j-1]][j-1];
minl[i][j]=min(minl[i][j-1],minl[p[i][j-1]][j-1]);
}
}
}
int Query(int u,int v)//询问
{
int ans=INF;
if(dep[u]<dep[v])swap(u,v);//u是深度大的结点
for(int j=14;j>=0;--j)//使得u,v深度相同
if(p[u][j]&&dep[p[u][j]]>=dep[v])
{
ans=min(ans,minl[u][j]);
u=p[u][j];
}
if(u==v)
return ans;
for(int j=14;j>=0;--j)//找到LCA并求解
{
if(p[u][j]!=p[v][j])
{
ans=min(ans,minl[u][j]);
ans=min(ans,minl[v][j]);
u=p[u][j];
v=p[v][j];
}
}
ans=min(ans,minl[u][0]);
ans=min(ans,minl[v][0]);
return ans;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;++i)
e[i]=(Line){read(),read(),read()};
sort(&e[1],&e[m+1]);
//克鲁斯卡尔求最大生成树
for(int i=1;i<=n;++i)f[i]=i;//并查集初始化
for(int i=1;i<n;++i)//克鲁斯卡尔
{
while(getf(e[cnt].u)==getf(e[cnt].v)&&cnt<=m)cnt++;//找到下一条可行的边
if(cnt>m)break;//不用连了，没有边了
f[getf(e[cnt].v)]=getf(e[cnt].u);//选择边
Add(e[cnt].u,e[cnt].v,e[cnt].w);
Add(e[cnt].v,e[cnt].u,e[cnt].w);
}
for(int i=1;i<=n;++i)//建树
if(!dep[i])
{
dep[i]=1;
Build(i,0);
}
Prepare();//LCA准备
Q=read();
while(Q--)
{
u=read();v=read();
if(getf(u)!=getf(v))//没有连在一起
printf("-1
");
else
printf("%d
",Query(u,v));
}
}