[NOIP2013/Codevs3287]货车运输-最小[大]生成树-树上倍增

Problem 树上倍增

题目大意

给出一个图，给出若干个点对u,v，求u,v的一条路径，该路径上最小的边权值最大。

Solution

看到这个题第一反应是图论。。

然而，任意路径最小的边权值最大，如果仔细思考的话就会知道，如果两个点相互连通，那么一定走的是最大生成树上的路径，而不会选择其他任何一条路径去走。

这个是可以非常简单证明的，就不再详述。

那么既然知道了这个，当然是先建一颗最大生成树啦！

现在问题来了，Prim&Kruskal，选哪个？

分析一下，prim复杂度$O(n^2)$,n为总点数。

Kruskal复杂度$O(m\log_2n)$,m为总边数。

显而易见，在这一道题目中kruskal更优。

于是写一个kruskal最大生成树。

接下来要在这颗树上跑。

我们设立一个fa数组，其fa[i][j]表示对于i节点，向上的2^j个节点编号是什么。显而易见，fa[i][0]就是i的父亲。

$$fa[i][j]=fa[fa[i][j-1][j-1]$$

然后我们还需要一个储存最小值的数组，设立minn数组，其中minn[i][j]表示对于i节点，向上2^j个节点的边最小值

显而易见，minn[i][0]就表示i节点本身链接父亲边的权值.

$$minn[i][j]=\min(minn[fa[i][j-1]][j-1],minn[i][j-1])$$

可以看出，这两个数组在O(n)的时间就可以求出来了。

接下来，对于每一个询问点对，我们只需要倍增求lca，再求两个点到lca路径上最小值，就可以求出答案。

判断uv谁深度更深，更深深度先跳到同一深度。

接下来两个一起向上跳，能够跳就跳。

具体方法可以看代码。

AC Code

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 struct kruskal{

     int u,v,w;

 }ekr[];

 struct node{

     int to,next,w;

 }e[];

 int f[],h[],dep[],n,m,u,v,w,q,ktot=,tot=,ans;

 int fa[][],minn[][];

 void add_kruskal(int u,int v,int w){

     ekr[++ktot].u=u;ekr[ktot].v=v;ekr[ktot].w=w;

 }

 bool cmp(kruskal a,kruskal b){

     return a.w>b.w;

 }

 void add(int u,int v,int w){

     e[++tot].to=v;e[tot].next=h[u];h[u]=tot;e[tot].w=w;

     e[++tot].to=u;e[tot].next=h[v];h[v]=tot;e[tot].w=w;

 }

 void initdfs(int x,int last,int we,int depth){

     dep[x]=depth;

     fa[x][]=last;

     minn[x][]=we;

     for(int i=;i<=;i++){

         fa[x][i]=fa[fa[x][i-]][i-];

         minn[x][i]=min(minn[x][i-],minn[fa[x][i-]][i-]);

     }

     for(int i=h[x];~i;i=e[i].next)

         if(e[i].to!=last)initdfs(e[i].to,x,e[i].w,depth+);

 }

 void queue(int u,int v){

     if(dep[u]<dep[v])swap(u,v);

     int dist=dep[u]-dep[v],tmp=;

     while(dist){

         if(dist%==)ans=min(ans,minn[u][tmp]),u=fa[u][tmp];

         tmp++;

         dist>>=;

     }

     for(int i=;i>=;i--){

         if(fa[u][i]!=fa[v][i]){

             ans=min(min(ans,minn[u][i]),minn[v][i]);

             u=fa[u][i];

             v=fa[v][i];

         }

     }

     ans=(u==v)?ans:min(min(ans,minn[u][]),minn[v][]);

 }

 int find(int x){

     if(f[x]!=x)f[x]=find(f[x]);

     return f[x];

 }

 int main(){

 //  freopen("xsy2018.in","r",stdin);

     memset(h,-,sizeof(h));

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++){

         scanf("%d%d%d",&u,&v,&w);

         add_kruskal(u,v,w);

     }

     sort(ekr+,ekr+ktot+,cmp);

     for(int i=;i<=n;i++)f[i]=i;

     for(int i=,sum=;i<=ktot;i++){

         int fu=find(ekr[i].u),fv=find(ekr[i].v);

         if(fu!=fv){

             add(ekr[i].u,ekr[i].v,ekr[i].w);

             f[fu]=fv;f[ekr[i].u]=fv;f[ekr[i].v]=fv;

             sum++;

         }

         if(tot==((n-)<<))break;

     }

     initdfs(,,,);

     scanf("%d",&q);

     for(int i=;i<=q;i++){

         scanf("%d%d",&u,&v);

         ans=;

         queue(u,v);

         printf("%d\n",(ans==)?-:ans);

     }

 }

巴特西

[NOIP2013/Codevs3287]货车运输-最小[大]生成树-树上倍增

Problem 树上倍增

题目大意

Solution

AC Code

最新文章

热门文章