UVa 11354 - Bond（最小生成树+倍增lca）

题目链接

简介：

最小瓶颈路，点对之间的路径中的最大边权

分析：

肯定是先求出最小生成树（一看到瓶颈路，就要往这方面想，当然也不是绝对的）

因为需要回答大量的查询，我们就需要把信息组织成某种易于查询的结构

一开始我认为可以直接像例一这样n^2处理，O(1)回答

但是n的范围不允许我这样干，

所以我们还是用最古老的方法：倍增

那么这道题就和货车运输有异曲同工之妙了

tip

代码量有点大

//这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

const int N=;
int n,m,q;
int st[N],tot=,fa[N],pre[N][],deep[N],maxx[N][],lg;
struct node{
    int x,y,v;
};
node e[N<<];
struct node2{
    int x,y,v,nxt;
};
node2 way[N<<];

int cmp(const node &a,const node &b){return a.v<b.v;}

int find(int x)
{
    if (fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void unionn(int f1,int f2){fa[f1]=f2;}

void add(int u,int w,int z)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
}

void Kruskal()
{
    sort(e+,e++m,cmp);
    int cnt=;
    for (int i=;i<=n;i++) fa[i]=i;
    for (int i=;i<=m;i++)
    {
        int f1=find(e[i].x);
        int f2=find(e[i].y);
        if (f1!=f2)
        {
            unionn(f1,f2);
            add(e[i].x,e[i].y,e[i].v);
            add(e[i].y,e[i].x,e[i].v);
            cnt++;
        }
        if (cnt==n-) break;
    }
}

void dfs(int now,int fa,int dep)
{
    deep[now]=dep;
    pre[now][]=fa;
    for (int i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa)
        {
            maxx[way[i].y][]=way[i].v;          //边权转移到靠下的点上 
            dfs(way[i].y,now,dep+);
        } 
}

void cl()
{
    lg=log(n)/log()+;
    for (int i=;i<=lg;i++)
        for (int j=;j<=n;j++)
        {
            pre[j][i]=pre[pre[j][i-]][i-];
            maxx[j][i]=max(maxx[j][i-],maxx[pre[j][i-]][i-]);
        }
}

int ask(int u,int w)
{
    int ans=;
    if (deep[u]<deep[w]) swap(u,w);
    int d=deep[u]-deep[w];
    if (d)
        for (int i=;i<=lg&&d;i++,d>>=)
            if (d&)
               ans=max(ans,maxx[u][i]),u=pre[u][i];
    if (u==w) return ans;
    for (int i=lg;i>=;i--)
        if (pre[u][i]!=pre[w][i])
        {
            ans=max(ans,maxx[u][i]);
            ans=max(ans,maxx[w][i]);
            u=pre[u][i];
            w=pre[w][i];
        }
    ans=max(ans,maxx[u][]);
    ans=max(ans,maxx[w][]);
    return ans;
}

int main()
{
    int cnt=;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        if (cnt++) puts("");

        memset(st,,sizeof(st));
        memset(pre,,sizeof(pre));
        memset(maxx,,sizeof(maxx));
        tot=;

        for (int i=;i<=m;i++)
        {
            int u,w,z;
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v);
        }

        Kruskal();
        dfs(,,);
        cl();

        scanf("%d",&q);
        for (int i=;i<=q;i++)
        {
            int u,w;
            scanf("%d%d",&u,&w);
            printf("%d\n",ask(u,w));
        }
    }
    return ;
}