题目：货车运输
大致题意：
给出一张无向带权图，对于m个询问（X，Y），要求找出X到Y的一条路径使得路径上的最小边权最大，并输出这个最小边权。
思路：
可以看出，X到Y的满足条件的路径一定在原图的最大生成树上。
update ： (2018/10/24) 证明的话网上好像没有，如图：
假设黑边是用kruskal求出的最大生成树，要求的是最左边的两个点间的最大的最小边权。
再假设绿色的边是这两点间的黑色路径中的最小值。
现在两点间连上一条红色的虚线边，要证明红色的边是小于绿色的边的。
根据kruskal算法的加边原理，我们知道只要不构成环，就会从大到小顺序加边。
假如红边大于绿边，那么红边在执行kruskal时一定先被遍历到，此时由于还没有遍历到绿边，所以红边是一定会被加入的（即如果红边加入后会形成环，那么绿边加入后也会形成环）。
但是由于红边不在最大生成树中，所以红边一定小于绿边。
尝试在这两点间寻找其他路径，同理可证最大的最小边权一定比最大生成树上的要小。
那么就可以用kruskal先预处理出原图的最大生成树，此时就可以用并查集判断出X到Y无路径的情况。
而找到这条路径，就可以采用倍增求LCA的方法。
即在倍增预处理anc[][]时，顺便处理一个边权v[][]，代表每个节点到他的第 2^i 层祖先的最大最小边权。
在倍增求LCA时，X和Y每向上跳一层，就用此时的v[][]更新ans。
注意图可能不连通。
ps：祝贺本蒟蒻博客300篇达成！
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 100000
#define maxm 500000
#define bin 22
#define inf (1<<30)struct Edge {
int x,y,z;Edge() {
}Edge(int xx,int yy,int zz) {
x=xx,y=yy,z=zz;}bool operator < (const Edge& oth) const {
return z>oth.z;}
};int n,m;
vector<Edge> e;
int fa[maxn+5]= {
0};vector<Edge> tr[maxn+5];
int f[maxn+5]= {
0};
int d[maxn+5]= {
0};int anc[maxn+5][bin+5]= {
0};
int v[maxn+5][bin+5]= {
0};void readin() {
scanf("%d%d",&n,&m);for(int i=1; i<=m; i++) {
int x,y,z;scanf("%d%d%d",&x,&y,&z);if(x>y) swap(x,y);e.push_back(Edge(x,y,z));}
}int find(int x) {
if(-1==fa[x]) return x;else return fa[x]=find(fa[x]);
}void init() {
sort(e.begin(),e.end());memset(fa,-1,sizeof(fa));
}void kruskal() {
init();for(int i=0; i<e.size(); i++) {
int x=e[i].x,y=e[i].y;int f1=find(x),f2=find(y);if(f1==f2) continue;fa[f1]=f2;tr[x].push_back(e[i]);tr[y].push_back(e[i]);}
}void make_tree(int x) {
anc[x][0]=f[x];for(int i=0; i<tr[x].size(); i++) {
int y=(tr[x][i].y==x?tr[x][i].x:tr[x][i].y);if(y==f[x]) continue;f[y]=x;d[y]=d[x]+1;v[y][0]=tr[x][i].z;make_tree(y);}
}void initLCA() {
for(int i=1; i<=bin; i++) {
for(int x=1; x<=n; x++) {
anc[x][i]=anc[anc[x][i-1]][i-1];v[x][i]=min(v[x][i-1],v[anc[x][i-1]][i-1]);}}
}int lca(int x,int y) {
int ans=inf;for(int i=bin; i>=0; i--) {
if(d[y]<=d[anc[x][i]]) {
ans=min(ans,v[x][i]);x=anc[x][i];}}if(x==y) return ans;for(int i=bin; i>=0; i--) {
if(anc[x][i]!=anc[y][i]) {
ans=min(ans,min(v[x][i],v[y][i]));x=anc[x][i],y=anc[y][i];}}ans=min(ans,min(v[x][0],v[y][0]));return ans;
}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");continue;}if(d[x]<d[y]) swap(x,y);int LCA=lca(x,y);printf("%d\n",LCA);}
}int main() {
readin();kruskal();for(int i=1; i<=n; i++) {
if(!f[i]) {
d[i]=1;make_tree(i);}}initLCA();query();return 0;
}
