首页 > 其他 > 详细

P2245 星际导航

时间:2019-02-09 16:10:31      阅读:161      评论:0      收藏:0      [点我收藏+]

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\n" , t) ; 
        else puts("impossible") ; 
    }   
    return 0 ; 
}

P2245 星际导航

原文:https://www.cnblogs.com/trouble-faker/p/10357547.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!