题目描述
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入输出格式
输入格式：
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道
路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。
输出格式：
输出文件名为 truck.out。
输出共有 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
嗯，感觉是很好的一道题qwq
思路：要求的是两点间所有路径中 满足 路径中的最小权值最大的一个权值
那么连点间权值较小的边完全可以舍弃（对答案无用），所以可以建一棵最大生成树，之后寻找两点的lca（显然选择lca答案最优），再求出路径 x—>lca(x,y)—>y 中所有边的最小权值就是答案
出错（决定以后把自己第一次写的代码哪里有问题记录下来qwq）：
将两点间的最小权值求成某一点其子树中的最小权值
code:
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=10010;
const int INF=0x3f3f3f3f;
int n,m,cnt;
int head[MAX],fa[MAX],dep[MAX],f[MAX][30],tree[MAX],fad[MAX];
int rd() { //快读
int x=0;
char c=' ';
while(c==' ' || c=='\n') c=getchar();
while(c<='9'&&c>='0') {
x=x*10+c-'0';
c=getchar();
}
return x;
}
struct edges{
int from,to,next,con;
void add(int x,int y,int z) {//感觉这样建邻接表舒服233
to=y,from=x,con=z,next=head[x],head[x]=cnt;
}
void print() {//中间输出用
printf("from=%d to=%d next=%d con=%d",from,to,next,con);
}
}edge[MAX*10],tr[MAX*2];
bool cmp(edges x,edges y) {
return x.con>y.con;
}
int get(int x) { //并查集
return fa[x]==x?x:fa[x]=get(fa[x]);
}
void dfs(int u) { //dfs 得到每个点深度 父亲 及到父亲的边的权值
int mi=INF;
for(int i=head[u];i;i=tr[i].next) {
int v=tr[i].to;
// cout<<v<<":"<<f[u][0]<<endl;
if(v!=f[u][0]) {
dep[v]=dep[u]+1;//深度
f[v][0]=u;//父亲
fad[v]=tr[i].con;//记录边权
dfs(v);
}
}
}
int getm(int u,int aim) { //求出路径中的最小权值
int mi=INF;
while(u!=aim) {
mi=min(mi,fad[u]);
u=f[u][0];
}
return mi;
}
int lca(int x,int y) { //倍增lca
int a=x,b=y;
if(dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y];
for(int i=0;d;d>>=1,i++)
if(d&1) x=f[x][i];
if(x!=y) {
for(int i=20;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
x=f[x][0];
}
return min(getm(a,x),getm(b,x)); //输出整个路径边权最小值
}
void init() { //倍增lca 预处理
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
if(f[i][j-1]!=-1)
f[i][j]=f[f[i][j-1]][j-1];
}
int main() {
n=rd(),m=rd();
for(int i=1;i<=m;i++) {
int a=rd(),b=rd(),c=rd();
edge[++cnt].add(a,b,c);
edge[++cnt].add(b,a,c);
}
sort(edge+1,edge+1+cnt,cmp);
// for(int i=1;i<=cnt;i++) {
// cout<<i<<"-";edge[i].print();cout<<endl;
// }
// cout<<endl;
for(int i=1;i<=n;i++) fa[i]=i;
memset(head,0,sizeof head);//预处理
int CNT=cnt;cnt=0;
for(int i=1;i<=CNT;i++) {//建最大生成树
// cout<<i<<"-";edge[i].print();cout<<endl;
int u=edge[i].from,v=edge[i].to;
u=get(u),v=get(v);
if(u!=v) {
fa[u]=v;
int a=edge[i].from,b=edge[i].to,c=edge[i].con;
tr[++cnt].add(a,b,c);
tr[++cnt].add(b,a,c);
// cout<<cnt-1<<"-";tr[cnt-1].print();cout<<endl;
// cout<<cnt<<"-"; tr[cnt].print();cout<<endl;
}
}
f[1][0]=-1;
dfs(1);
init();
int q=rd();
while(q--) {
int x=rd(),y=rd();
if(get(x)!=get(y)) printf("-1\n");
//特判 当两点不在同一并查集中时（说明至少有一个不在生成树中）就说明连不到这个点
else printf("%d\n",lca(x,y));
}
return 0;
}