大学生免费ppt网站/短链接在线生成免费

https://www.luogu.org/problem/P2245
题目描述
\text{sideman}sideman 做好了回到 \text{Gliese}Gliese 星球的硬件准备，但是 \text{sideman}sideman 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

\text{sideman}sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 (A, B)(A,B)，\text{sideman}sideman 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的危险程度值最小可能是多少。作为 \text{sideman}sideman 的同学，你们要帮助 \text{sideman}sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式
第一行包含两个正整数 NN 和 MM，表示点数和边数。

之后 MM 行，每行三个整数 AA，BB 和 LL，表示顶点 AA 和 BB 之间有一条边长为 LL 的边。顶点从 11 开始标号。

下面一行包含一个正整数 QQ，表示询问的数目。

之后 QQ 行，每行两个整数 AA 和 BB，表示询问 AA 和 BB 之间最危险的边危险程度的可能最小值。

输出格式
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 \text{impossible}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%40% 的数据，满足 N \leq 1000, M \leq 3000, Q \leq 1000N≤1000,M≤3000,Q≤1000。

对于 80%80% 的数据，满足 N \leq 10000, M \leq 10^5, Q \leq 1000N≤10000,M≤10
5
,Q≤1000。

对于 100%100% 的数据，满足 N \leq 10^5, M \leq 3 \times 10^5, Q \leq 10^5, L \leq 10^9N≤10
5
,M≤3×10
5
,Q≤10
5
,L≤10
9
。数据不保证没有重边和自环。
思路：题目意思就是选择一条从$u$到$v$的路径，使得这条路径上权值最大的权值是所有情况中最小的。此时不难联想到最小生成树，因为克鲁斯卡尔算法就是以贪心的策略，保证每次选出的边都是当前权值最小的。那么我们先建立出最小生成树，此时问题就转换了找$u$到$v$的树链上的最大值，用$LCA$就可以解决辣。即在倍增求$LCA$算法中用一个$dis$数组同样倍增的来记录。当然要是不嫌麻烦的话，也可以用树剖+线段树解决。

#include<bits/stdc++.h>
using namespace std;const int maxn=1e5+5;
const int maxm=3e5+5;struct edge
{int from,to,nxt,dis;bool operator <(const edge &a)const{return dis<a.dis;}
};edge e[maxm];
edge Edge[maxn<<1];
int head[maxn],f[maxn],fa[maxn][30],dis[maxn][30],deep[maxn],a[maxn],bs[30];
int n,m,tot,cnt;void dfs(int u,int fath)
{deep[u]=deep[fath]+1;fa[u][0]=fath;dis[u][0]=a[u];for(int i=1;i<=20;i++){fa[u][i]=fa[fa[u][i-1]][i-1];dis[u][i]=max(dis[u][i-1],dis[fa[u][i-1]][i-1]);}int to;for(int i=head[u];i;i=Edge[i].nxt){to=Edge[i].to;if(to!=fath)a[to]=Edge[i].dis,dfs(to,u);}
}int work(int u,int v)
{if(deep[u]<deep[v])swap(u,v);int tmp=deep[u]-deep[v];int ans=0;for(int i=20;i>=0;i--)if(bs[i]&tmp)ans=max(ans,dis[u][i]),u=fa[u][i];if(u==v)return ans;for(int i=20;i>=0;i--)if(fa[u][i]!=fa[v][i])ans=max(ans,max(dis[u][i],dis[v][i])),u=fa[u][i],v=fa[v][i];return max(ans,max(dis[u][0],dis[v][0]));
}void addedge(int u,int v,int dis)
{Edge[++cnt].to=v,Edge[cnt].dis=dis,Edge[cnt].nxt=head[u],head[u]=cnt;
}void init()
{for(int i=1;i<=n;i++)f[i]=i;for(int i=0;i<=20;i++)bs[i]=1<<i;
}int father(int x)
{return f[x]==x?x:f[x]=father(f[x]);
}bool check(int x,int y)
{int fx=father(x),fy=father(y);if(fx!=fy){f[fx]=fy;return 1;}return 0;
}int main()
{scanf("%d%d",&n,&m);init();int u,v,dis;for(int i=0;i<m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].dis);sort(e,e+m);for(int i=0;i<m;i++){if(check(e[i].from,e[i].to))addedge(e[i].from,e[i].to,e[i].dis),addedge(e[i].to,e[i].from,e[i].dis);}for(int i=1;i<=n;i++){if(!deep[i])dfs(i,0);}int q;scanf("%d",&q);while(q--){scanf("%d%d",&u,&v);if(father(u)!=father(v))printf("impossible\n");elseprintf("%d\n",work(u,v));}return 0;
}