P2245 星际导航

Kruskal 重构树裸题

Lrt 大佬它说这是 最小瓶颈路 裸题，还比我快了1倍，呵呵，鄙人当然知道，就是不会

题面

sideman 做好了回到 Gliese 星球的硬件准备，但是 sideman 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 N 个顶点和 M 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

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

看代码吧

#include <bits/stdc++.h>
#define ll long long 
#define E 1000007
using namespace std ; 
ll read() { ll aa ; scanf("%lld" , &aa) ; return aa ; } 
ll n , m , head[E] , q , fa[E] , N , f[E][20] , dian[E] , dep[E] ; 
struct eg {
	ll ui , vi , wi ; 
	bool operator < (const eg & x) const {
		return wi < x.wi ; 
	}
} xian[E] ; 
struct edge { ll pre , to ; } bian[E << 1] ; 
void add(ll u , ll v) { bian[++q].pre = head[u] ; bian[q].to = v ; head[u] = q ; }
ll find(ll x) { return fa[x] == x ? x : fa[x] = find(fa[x]) ; } 
void dfs(ll u , ll fath) {
	dep[u] = dep[fath] + 1 ; 
	for(int i = head[u] ; i ; i = bian[i].pre) {
		if(bian[i].to == fath) continue ; 
		dfs(bian[i].to , u) ; 
	}
}
ll lca(ll x , ll y) {
	if(dep[x] < dep[y]) swap(x , y) ; 
	for(int j = 19 ; j >= 0 ; j --) 
		if(dep[f[x][j]] >= dep[y]) x = f[x][j] ; 
	if(x == y) return x ; 
	for(int j = 19 ; j >= 0 ; j --) 
		if(f[x][j] != f[y][j]) x = f[x][j] , y = f[y][j] ; 
	return f[x][0] ; 
}	
int main() {
	n = read() , m = read() ; 
	for(int i = 1 , xi , yi , zi ; i <= m ; i ++) {
		xi = read() , yi = read() , zi = read() ; 
		xian[i] = (eg){xi , yi , zi} ; 
	}
	sort(xian+1 , xian+m+1) ; 
	for(int i = 1 ; i < n*2 ; i ++) fa[i] = i ; 
	N = n ; 
	for(int i = 1 ; i <= m ; i ++) {
		ll fu = find(xian[i].ui) , fv = find(xian[i].vi) ; 
		if(fu == fv) continue ; 
		f[fu][0] = f[fv][0] = fa[fu] = fa[fv] = ++N ;
		dian[N] = xian[i].wi ;  
		add(fu , N) , add(N , fu) , add(fv , N) , add(N , fv) ; 
		if(N == n*2-1) break ; 
	}
	for(int j = 1 ; j <= 19 ; j ++) 
		for(int i = 1 ; i <= N ; i ++) 
			f[i][j] = f[ f[i][j-1] ][ j-1 ] ; 
	dep[N] = 1 ; 
	dfs(N , 0) ; 	
	
	ll Q = read() ; 
	while(Q --) {
		ll u = read() , v = read() ; 
		ll t = dian[lca(u , v)] ;
		if(t) printf("%lld
" , t) ; 
		else puts("impossible") ; 
	}	
	return 0 ; 
}