题面

题目描述

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。数据不保证没有重边和自环。

题解

这道题和的本质是一模一样的

显然可以用更好的方法来解决（网络流、树链剖分等）

但是我这个蒟蒻用最弱的方法：最小生成树+LCA

---

但是，一定有人会有疑问，为什么是最小生成树

我们可以简单的证明一下

假设当前的两个节点之间，最小生成树上的最大边权是x

但是存在另外一条路径的边权的最大值是x'，且x‘ < x

这种情况会不会存在？

最小生成树是将边按照权值排序后再来链接

如果存在x'所在的这一条路径的话,必定会优先选择x'所在的路径

而不是x所在的路径

（为什么请自己考虑一下）

那么，知道结果必定在最小生成树上

问题迎刃而解

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAX 110000#define MAXL 510000#define INF 0inline 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
          
           =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
           
            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\n"); else printf("%d\n",Query(u,v)); }}