题意：

给一个无向图，k个询问求节点a到节点b最长边的最小值。n，k≤15000。

题解：

”最长边的最小值“经常可以用最小生成树解决，因为生成树里的每一条边都是可取的最小边，求完生成树之后就是经典的倍增应用：求lca的时候顺便维护一下边权最大值即可。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 30010 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;    14 }15 struct abc{
   int f,t,w;}abcd[maxn]; bool cmp(abc a,abc b){
   return a.w
         
          =0;i--)if(fa[i][x]!=fa[i][y])30         ans=max(ans,mx[i][x]),ans=max(ans,mx[i][y]),x=fa[i][x],y=fa[i][y];31     if(x==y)return ans;else{ans=max(ans,mx[0][x]); ans=max(ans,mx[0][y]); return ans;}32 }33 int main(){34     n=read(); m=read(); k=read(); inc(i,1,n)p[i]=i;35     inc(i,1,m){
   int x=read(),y=read(),z=read(); abcd[i]=(abc){x,y,z};} sort(abcd+1,abcd+m+1,cmp);36     inc(i,1,m){37         int x=find(abcd[i].f),y=find(abcd[i].t); if(x!=y)pe(x,y,abcd[i].w),p[x]=y,tot++; if(tot==n-1)break;38     }39     dfs(1);40     for(int i=1;(1<
          
           <=n;i++)inc(j,1,n)41 fa[i][j]=fa[i-1][fa[i-1][j]],mx[i][j]=max(mx[i-1][j],mx[i-1][fa[i-1][j]]);42 inc(i,1,k){ int x=read(),y=read(); printf("%d\n",lca(x,y));}43 return 0;44 }
          
         
        
       
      
     

 

20161115