题目描述
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。数据不保证没有重边和自环。
实际上，更快的做法是使用Kruskal重构树！
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN = ;
const int M = ; int tot,rt;
int val[MAXN];
inline int newnode(){return ++tot;} struct Undirected_Edge{
int x,y,w;
bool operator <(const Undirected_Edge &rhs){
return w<rhs.w;
}
}edges[M<<];
int n,m,q; struct Edge{
int next,to;
}e[MAXN<<];
int ecnt,head[MAXN];
inline void add(int x,int y){
e[++ecnt].to = y;
e[ecnt].next = head[x];
head[x] = ecnt;
} int fa[MAXN],dep[MAXN],siz[MAXN],hch[MAXN];
void dfs1(int cur,int pre){
fa[cur]=pre;dep[cur]=dep[pre]+;siz[cur]=;
int mx=-;
for(int i=head[cur];i;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
dfs1(v,cur);
siz[cur]+=siz[v];
if(siz[v]>mx) hch[cur]=v,mx=siz[v];
}
}
int top[MAXN];
void dfs2(int cur,int tp){
top[cur]=tp;
if(hch[cur]) dfs2(hch[cur],tp);
for(int i=head[cur];i;i=e[i].next){
int v=e[i].to;
if(v==fa[cur]||v==hch[cur]) continue;//
dfs2(v,v);
}
} int lca(int x,int y){
while(top[x]!=top[y]){
dep[top[x]]>=dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
}
return dep[x]<=dep[y]?x:y;
}
struct ufs{
int fa[MAXN];
int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
void cat(int x,int y){x=fnd(x);y=fnd(y);if(x==y)return;fa[x]=y;}
}U; int main(){
n=rd();m=rd();
int x,y,w,u,v,cur;tot=n;
for(int i=;i<=n*;i++) U.fa[i]=i;
for(int i=;i<=m;i++){
edges[i].x = rd();
edges[i].y = rd();
edges[i].w = rd();
}
sort(edges+,edges++m);
int edge_cnt=;
for(int i=;i<=m;i++){
x=edges[i].x,y=edges[i].y,w=edges[i].w;
u=U.fnd(x);v=U.fnd(y);
if(u==v)continue;
edge_cnt++;
cur=newnode();
U.cat(u,cur);U.cat(v,cur); val[cur]=w;
add(u,cur);add(v,cur);
add(cur,u);add(cur,v);
if(edge_cnt==n-)break;
}
for(int i=;i<=tot;i++){
if(siz[i])continue;
v=U.fnd(i);
dfs1(v,);dfs2(v,v);
}
q=rd();
for(int i=;i<=q;i++){
x=rd();y=rd();
if(U.fnd(x)!=U.fnd(y)) {puts("impossible");continue;}
printf("%d\n",val[lca(x,y)]);
} return ;
}
Kruskal重构树
求最大值的最小值，先求出最小生成树，同时建图·再倍增LCA，同时设立g数组倍增最大值。
//Stay foolish,stay hungry,stay young,stay simple
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; const int MAXN=; int n,m,q; struct Edge{
int x,y,w;
}e[MAXN];
int ecnt;
inline void add(int x,int y,int w){
e[++ecnt].x = x;
e[ecnt].y = y;
e[ecnt].w = w;
}
bool cmp(const Edge &x,const Edge &y){
return x.w < y.w ;
} struct Tree{
int next,to,w;
}t[MAXN];
int tcnt=,thead[MAXN*];
inline void tadd(int x,int y,int w){
t[++tcnt].next = thead[x];
t[tcnt].to = y;
t[tcnt].w = w;
thead[x]=tcnt;
} int fa[MAXN];
int fnd(int x){
return x==fa[x]?x:fa[x]=fnd(fa[x]);
}
void cat(int x,int y){
x=fnd(x);y=fnd(y);
fa[y]=x;
} void kls(){
int cnt=;
sort(e+,e++m,cmp);
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++){
Edge now=e[i];
int x=fnd(now.x),y=fnd(now.y);
if(x==y) continue;
tadd(now.x,now.y,now.w);//x y
tadd(now.y,now.x,now.w);
cat(x,y);
if(++cnt>=n) break ;
}
} int f[MAXN][],g[MAXN][],dep[MAXN];
void dfs(int now,int pre){
// if(dep[now]) return ;
for(int i=thead[now];i;i=t[i].next){
int v=t[i].to ;
if(dep[v]) continue;
if(v==pre) continue;
f[v][]=now;
g[v][]=t[i].w;
dep[v]=dep[now]+;
dfs(v,now);
}
}
void redouble(){
for(int j=;(<<j)<=n;j++){
for(int i=;i<=n;i++){
f[i][j]=f[f[i][j-]][j-];
g[i][j]=max(g[i][j-],g[f[i][j-]][j-]);
// cout<<g[i][j]<<" "<<i<<" "<<j<<" !"<<endl;
}
}
}
int query(int x,int y){
int ret=-;
if(dep[x]<dep[y]) swap(x,y);
for(int i=;i>=;i--){
if(!f[x][i]) continue;
// if(dep[x]-(1<<i)<y) continue;
if(dep[f[x][i]]<dep[y]) continue;
ret=max(ret,g[x][i]);//顺序
// cout<<"X:"<<x<<" "<<i<<endl;
x=f[x][i]; }
// if(dep[x]>dep[y]){
// x=f[x][0];
// ret=max(ret,g[x][0]);
// }
// if(y==0) x=f[x][0];
// cout<<dep[x]<<" "<<dep[y]<<"DEP\n";
if(x==y) return ret;
for(int j=log2(n);j>=;j--){
if(f[x][j]==f[y][j]) continue;
ret=max(ret,max(g[x][j],g[y][j]));
x=f[x][j];y=f[y][j];
}
return max(ret,max(g[x][],g[y][]));
} //
void print(int now,int pre){
cout<<pre<<"--"<<now<<endl;
for(int i=thead[now];i;i=t[i].next){
int v=t[i].to ;
if(v==pre) continue;
print(v,now);
}
}
void debug(){
// print(1,0);
// for(int i=1;i<=n;i++) cout<<dep[i]<<" ";
// for(int i=1;i<=n;i++){
// for(int j=0;j<=log2(n);j++){
// cout<<g[i][j]<<" ";
// }
// cout<<endl;
// } }
//
int main(){
cin.sync_with_stdio(false);
cin.tie();
cin>>n>>m;
for(int i=;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
add(x,y,w);
}
kls();
for(int i=;i<=n;i++){
if(!dep[i]) dep[i]=,dfs(i,);
}
redouble();
cin>>q;
for(int i=;i<=q;i++){
int x,y;
cin>>x>>y;
if(fnd(x)!=fnd(y)) cout<<"impossible\n";
else cout<<query(x,y)<<endl;
}
// debug(); return ;
}