星际导航

(nav.pas/c/cpp/in/out,1s,64MB)

题目描述

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。

样例输入

4 5

1 2 5

1 3 2

2 3 11

2 4 6

3 4 4

2 3

1 4

1 2

样例输出

数据范围与约定

对于40% 的数据，满足N≤1000，M≤3000，Q≤1000。

对于 80% 的数据，满足N≤10000，M≤105，Q≤1000。

对于 100% 的数据，满足N≤105，M≤3×105，Q≤105，L≤109。数据不保证没有重边和自环。

　　这种题的模型很常见，先最小生成树，再深搜处理出fat[],next[],d[]数组，分别表示生成树后每个节点的父亲，到父亲的路径权值，和此节点的深度，然后就可以一步一步先上搜，或者LCA更新答案。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #include<queue>
  9 #include<fstream>
 10 using namespace std;
 11 inline int read(){
 12     int x=0,f=1;char ch=getchar();
 13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 14     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 15     return x*f;
 16 }
 17 int N,M,Q;
 18 struct node{
 19     int x,y,w;
 20 }e[300005];
 21 struct node1{
 22     int x,y;
 23 }q[100005];
 24 int cmp(const node&a,const node&b){
 25     if(a.w<b.w) return 1;
 26     return 0;
 27 }
 28 int fa[100005];
 29 int getfa(int u){
 30     if(u!=fa[u]) fa[u]=getfa(fa[u]);
 31     return fa[u];
 32 }
 33 vector<int>to[100005],cost[100005];
 34 inline void dfs(int,int);
 35 inline int get_ans(int,int);
 36 int d[100005];
 37 int fat[100005];
 38 int next[100005];
 39 int main(){
 40     //freopen("nav.in","r",stdin);
 41     //freopen("nav.out","w",stdout);
 42     N=read(); M=read();
 43     for(int i=1;i<=M;i++){
 44         int u,v,c;
 45         u=read(); v=read(); c=read();
 46         e[i].x=u; e[i].y=v; e[i].w=c;
 47     }
 48     Q=read();
 49     for(int i=1;i<=Q;i++){
 50         int u,v;
 51         u=read(); v=read();
 52         q[i].x=u; q[i].y=v;
 53     }
 54     sort(e+1,e+M+1,cmp);
 55     for(int i=1;i<=N;i++) fa[i]=i;
 56     for(int i=1;i<=M;i++){
 57         int u=e[i].x; int v=e[i].y; int c=e[i].w;
 58         int fau=getfa(u); int fav=getfa(v);
 59         if(fau!=fav){
 60             if(fau<fav) fa[fav]=fa[fau];
 61             else fa[fau]=fa[fav];
 62             to[u].push_back(v); to[v].push_back(u);
 63             cost[u].push_back(c); cost[v].push_back(c);
 64         }
 65     }
 66     for(int i=1;i<=N;i++){
 67         if(fa[i]==i){
 68             dfs(i,1);
 69             break;
 70         }
 71     }
 72     for(int i=1;i<=Q;i++){
 73         int u=q[i].x; int v=q[i].y;
 74         if(getfa(u)!=getfa(v)){
 75             cout<<"impossible"<<endl;
 76             continue;
 77         }
 78         printf("%d\n",get_ans(u,v));
 79     }
 80     return 0;
 81 }
 82 inline void dfs(int root,int deep){
 83     d[root]=deep;
 84     for(int i=0;i<to[root].size();i++){
 85         int g=to[root][i];
 86         if(d[g]==0){
 87             dfs(g,deep+1);
 88             fat[g]=root;
 89             next[g]=cost[root][i];
 90         }
 91     }
 92 }
 93 int get_ans(int u,int v){
 94     int x=u,y=v,ans=0;
 95     while(x!=y){
 96         if(d[x]<d[y]) y=fat[y];
 97         else if(d[x]>d[y]) x=fat[x];
 98         else if(d[x]==d[y]) x=fat[x],y=fat[y];
 99     }
100     while(u!=x) ans=max(ans,next[u]),u=fat[u];
101     while(v!=y) ans=max(ans,next[v]),v=fat[v];
102     return ans;
103 }

星际导航

推荐阅读