蓝桥杯2023年第十四届省赛真题-网络稳定性

解题思路:先用最小生成树的方法生成一个最大生成树,在使用倍增做lca的同时将最小值找出来(类似于st表,st也是用倍增,相当于使用倍增同时搞出lca与st表)

注意事项:读入与输出较大,使用较快的输入输出,不然会超时

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int from;
    int to;
    int w;
    int next; 
}mp[1000005];
vector<node>v;
int head[100005],cnt=0;
void add(int a,int b,int c)
{
    mp[++cnt].to=b;
    mp[cnt].next=head[a];
    mp[cnt].w=c;
    head[a]=cnt;
}
bool cmp(node a,node b)
{
    return a.w>b.w;
}
int f[1000005];
int fand(int x)
{
    if(f[x]!=x)
    {
        return f[x]=fand(f[x]);
    }
    return x;
}
void meare(node a)
{
    int x,y;
    x=fand(a.from);
    y=fand(a.to);
    if(x!=y)
    {
        add(a.from,a.to,a.w);
        add(a.to,a.from,a.w);
        f[y]=x;
    }
}
int deep[1000005];
int st[1000005][25];
int stmax[1000005][25];
void dfs(int u,int fa,int w)
{
    deep[u]=deep[fa]+1;
    st[u][0]=fa;
    stmax[u][0]=w;
    for(int i=1;i<=19;i++)
    {
        st[u][i]=st[st[u][i-1]][i-1];
        stmax[u][i]=min(stmax[u][i-1],stmax[st[u][i-1]][i-1]);
         
    }
    for(int i=head[u];i;i=mp[i].next)
    {
        int v;
        v=mp[i].to;
        if(v!=fa)
        {
            dfs(v,u,mp[i].w);
        }
    }
}
int lca(int a,int b)
{
    int ans=1E9;
    if(deep[a]<deep[b])swap(a,b);
    for(int i=19;i>=0;i--)
    {
        if(deep[st[a][i]]>=deep[b])
        {
            ans=min(ans,stmax[a][i]);
            a=st[a][i];
             
        }
    }
    if(a==b)return ans;
    for(int i=19;i>=0;i--)
    {
        if(st[a][i]!=st[b][i])
        {
            ans=min(ans,stmax[a][i]);
            ans=min(ans,stmax[b][i]);
            a=st[a][i];
            b=st[b][i];
        }
    }
    ans=min(ans,stmax[a][0]);
    ans=min(ans,stmax[b][0]);
    return ans;
}
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        node a;
        scanf("%d%d%d",&a.from,&a.to,&a.w);
        v.push_back(a);
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++)
    {
        meare(v[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(deep[i]==0)dfs(i,0,0);
    }
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int ans;
        ans=lca(x,y);
        if(fand(x)!=fand(y))
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
    return 0;
}