生成树相关问题

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

第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<edge *> & T,vector<int> * G){
 4         for(int i=0;i<T.size();i++){
 5             edge & e=*T[i];
 6             G[e.v1].push_back(i);
 7         }
 8     }
 9     static void dfs(vector<edge *> & T,vector<int> * G,int * fa,int u,int fthr){
10         vector<int> & g=G[u];
11         for(int i=0;i<g.size();i++){
12             edge & e=*T[g[i]];
13             if(e.v2!=fa)dfs(T,G,fa,e.v2,p[e.v2]=u);
14         }
15     }
16 };

接下来通过预处理计算出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<n;i++){
 3         anc[i][0]=fa[i];maxcost[i][0]=cost[i];
 4         for(int j=1;(1<<j)<n;j++)anc[i][j]=-1;
 5         }
 6     for(int j=1;(1<<j)<n;j++)
 7         for(int i=0;i<n;i++)
 8             if(anc[i][j-1]!=-1){
 9                 int a=anc[i][j-1];
10                 anc[i][j]=anc[a][j-1];
11                 maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
12             }
13  }

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

int query(int p,int q){
    int tmp;int log=0;if(L[p]<L[q])swap(p,q);
    while((1<<(log+1))<=L[p])log++;int ans=-INF;
    for(int i=log;i>=0;i--)
        if(L[p]-(1<<i)>=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）的时间内解决了本题。

生成树相关问题

相关推荐