题面
题目描述
sideman做好了回到Gliese 星球的硬件准备，但是sideman的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有N 个顶点和M 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。
sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问(A, B)，sideman 想知道从顶点A 航行到顶点B 所经过的最危险的边的危险程度值最小可能是多少。作为sideman 的同学，你们要帮助sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。
输入格式：
第一行包含两个正整数N 和M，表示点数和边数。
之后 M 行，每行三个整数A，B 和L，表示顶点A 和B 之间有一条边长为L 的边。顶点从1 开始标号。
下面一行包含一个正整数 Q，表示询问的数目。
之后 Q 行，每行两个整数A 和B，表示询问A 和B 之间最危险的边危险程度的可能最小值。
输出格式：
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出impossible。
输入输出样例
输入样例#1：
4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2
输出样例#1：
5
4
5
说明
对于40% 的数据，满足N≤1000，M≤3000，Q≤1000。
对于 80% 的数据，满足N≤10000，M≤105，Q≤1000。
对于 100% 的数据，满足N≤105，M≤3×105，Q≤105，L≤109。数据不保证没有重边和自环。
题解
这道题和NOIP2013货车运输的本质是一模一样的
显然可以用更好的方法来解决（网络流、树链剖分等）
但是我这个蒟蒻用最弱的方法：最小生成树+LCA
但是，一定有人会有疑问，为什么是最小生成树
我们可以简单的证明一下
假设当前的两个节点之间，最小生成树上的最大边权是x
但是存在另外一条路径的边权的最大值是x'，且x‘ < x
这种情况会不会存在？
最小生成树是将边按照权值排序后再来链接
如果存在x'所在的这一条路径的话,必定会优先选择x'所在的路径
而不是x所在的路径
（为什么请自己考虑一下）
那么，知道结果必定在最小生成树上
问题迎刃而解
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 110000
#define MAXL 510000
#define INF 0
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][21],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]=max(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=20;j>=0;--j)//使得u,v深度相同
if(p[u][j]&&dep[p[u][j]]>=dep[v])
{
ans=max(ans,minl[u][j]);
u=p[u][j];
}
if(u==v)
return ans;
for(int j=20;j>=0;--j)//找到LCA并求解
{
if(p[u][j]!=p[v][j])
{
ans=max(ans,minl[u][j]);
ans=max(ans,minl[v][j]);
u=p[u][j];
v=p[v][j];
}
}
ans=max(ans,minl[u][0]);
ans=max(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("impossible
");
else
printf("%d
",Query(u,v));
}
}