NOIP2013 货车运输

  1 #include<bits/stdc++.h>
  2 #define inf 20200306
  3 using namespace std;
  4 int n,m,u,v,w,cnt,q;
  5 int f[100005][21],wi[100005][21],head[100005],d[10005],fa[100005],vis[100005];
  6 struct Edget{int u,v,w;}et[100005];
  7 struct Edge{int v,next,w;}e[100005];
  8 bool cmp(Edget a,Edget b){return a.w>b.w;}
  9 int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
 10 void add(int u,int v,int w){
 11     e[++cnt].v=v;
 12     e[cnt].w=w;
 13     e[cnt].next=head[u];
 14     head[u]=cnt;
 15 } 
 16 
 17 void kruskal(){
 18     sort(et+1,et+1+m,cmp);
 19     for(int i=1;i<=n;++i)fa[i]=i;
 20     for(int i=1;i<=m;++i){
 21         int u=et[i].u,v=et[i].v,w=et[i].w;;
 22         if(find(u)!=find(v)){
 23             fa[find(u)]=find(v);
 24             add(u,v,w);
 25             add(v,u,w);
 26         }
 27     }
 28 }
 29 
 30 void dfs(int u){
 31   vis[u]=1;
 32   for(int i=head[u];i;i=e[i].next){
 33     int v=e[i].v;
 34     if(!vis[v]){
 35       d[v]=d[u]+1;
 36       f[v][0]=u;
 37       wi[v][0]=e[i].w;
 38       dfs(v);
 39     }
 40   }
 41   return;
 42 }
 43 
 44 int lca(int x,int y){
 45   if(find(x)!=find(y)) return -1;
 46   int ans=inf;
 47  
 48   if(d[x]<d[y])swap(x,y);
 49   int k=d[x]-d[y];
 50   for(int j=20;j>=0;j--){
 51     if(k&(1<<j)){
 52       ans=min(ans,wi[x][j]);
 53       x=f[x][j];
 54     }
 55   }
 56   if(x==y)return ans;
 57   
 58   for(int j=20;j>=0;j--){
 59     if(f[x][j]!=f[y][j]){ 
 60       ans=min(ans,min(wi[x][j],wi[y][j]));
 61       x=f[x][j],y=f[y][j];
 62     }
 63   }
 64   ans=min(ans,min(wi[x][0],wi[y][0]));
 65   return ans;
 66 }
 67 
 68 int main(){
 69   ios::sync_with_stdio(false);
 70   
 71   cin>>n>>m;
 72   for(int i=1;i<=m;++i){
 73       cin>>u>>v>>w;
 74       et[i].u=u;
 75     et[i].v=v;
 76     et[i].w=w; 
 77     }
 78     
 79     kruskal();
 80   
 81   for(int i=1; i<=n; i++)
 82     if(!vis[i]){ //dfs仅收集信息 
 83       d[i]=1; 
 84       dfs(i);
 85       f[i][0]=i;
 86       wi[i][0]=inf;
 87    }
 88   
 89   for(int i=1; i<=20; i++)
 90     for(int j=1; j<=n; j++){
 91       f[j][i]=f[f[j][i-1]][i-1]; 
 92       wi[j][i]=min(wi[j][i-1], wi[f[j][i-1]][i-1]);
 93    }
 94   
 95   cin>>q;
 96   while(q--){
 97     cin>>u>>v;
 98     cout<<lca(u,v)<<endl;
 99   }
100   return 0;
101 }