算法竞赛入门经典训练指南

第5章 图论算法与模型

5.4 生成树相关问题

例题21 bond UVa11354

有n座城市通过m条双向道路相连，每条道路有一个危险系数。你的任务是回答若干个询问，每个询问包含一个起点s和一个终点t，要求找到一条s到t的路，使得路径所有边的最大危险系数最小。

相似的题

noip 2013 day1 truck

【分析】本题也是要求瓶颈路，但需要快速回答很多查询。这很像前面数据结构部分的题目，因此也可考虑先做预处理，把信息组织成某种易于查询的结构。

首先求出最小生成树，并把它改写成有根树，让fa[i]和cost[i]分别节点i的父亲编号和它与父亲之间的边权，L[i]表示节点i的深度（根节点的深度为0，根节点的子节点深度为1，以此类推）。

无根树转有根树的代码如下。

1 class SetRoot{ 2 public: 3     static void pretreat(vector
     
       & T,vector
      
        * G){ 4         for(int i=0;i
       
         & T,vector
        
          * G,int * fa,int u,int fthr){10         vector
         
           & g=G[u];11         for(int i=0;i
         
        
       
      
     

 

接下来通过预处理计算出anc数组和maxcost数组，其中anc[i][j]表示节点i的第2^j 级祖先编号（anc[i][0]就是fa[i]，anc[i][j]=-1表示该祖先不存在），maxcost[i][j]表示节点i和它的2^j级祖先之间路径上的最大值。预处理代码如下。

1 void prepoccess(){ 2     for(int i=0;i

 有了这些预处理我们就可以编写查询处理过程了。假定查询的两个节点为p和q，并且p比q深（如果不是的话，交换），则可以先把p提升到和q同一级的位置，然后用类似二进制展开的方法不断把p和q同时往上“提”（要保证二者深度始终相等），同时更新最大边权。代码如下。

int query(int p,int q){    int tmp;int log=0;if(L[p]
     
      =0;i--)        if(L[p]-(1<
      
       =L[q]){            ans=max(ans,maxcost[p][i]);            p=anc[p][i];        }    if(p==q)return ans;//LCA(p,q)=p    for(int i=log;i>=0;i--)        if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){            ans=max(ans,maxcost[p][i]);            p=anc[p][i];            ans=max(ans,maxcost[q][i]);            q=anc[q][i];        }        ans=max(ans,cost[p]);    ans=max(ans,cost[q]);    return ans;//LCA(p,q)=fa[p]=fa[q];}
      
     

 上述代码也能求出p和q的最近公共祖先（见注释）。这样，就在预处理O（nlogn），和查询O（logn）的时间内解决了本题。