[ABC235E] MST + 1 题解

· · 题解

思路概述

考虑最小生成树。

显然，若新加的边一定在新图的最小生成树中，那把这条边一定替换掉了原图最小生成树中的一条边。

所以，我们判断新加的边是否一定会在新图的最小生成树中，只需要判断，原图最小生成树中，新加的边的两个端点之间路径的边权最大值是否大于这条新加的边的边权，若大于则一定可以加进去，否则不一定。

解法实现

  1. 对原图求最小生成树，并建新图。

  2. 对于新加的边，在刚刚建立的新图上求两端点之前路径边权最大值（考虑 最近公共祖先或树剖），按照上面的想法判断即可。

code

代码较丑不喜勿喷。


#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+10,M=N*2;

int n,m,q;
struct edge{
    int u,v,w;
    bool operator<(const edge &x)   const
    {
        return w<x.w;
    }
}ed[N];
int fa[N];
int h[N],e[M],ne[M],w[M],tot;
int f[N][22],g[N][22],dep[N];

int find(int x)
{
    if(fa[x]==x)    return x;
    return fa[x]=find(fa[x]);
}
void add(int a,int b,int c)
{
    e[++tot]=b;w[tot]=c;ne[tot]=h[a];h[a]=tot;
}
void dfs(int x,int FA)
{
    dep[x]=dep[FA]+1;
    f[x][0]=FA;
    for(int i=1;i<=20;i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
        g[x][i]=max(g[x][i-1],g[f[x][i-1]][i-1]);
    }
    for(int i=h[x];i;i=ne[i])
    {
        int j=e[i];
        if(j==FA)   continue;
        g[j][0]=w[i];
        dfs(j,x);
    }
}
int get_lca(int a,int b)
{
    if(dep[a]<dep[b])   swap(a,b);
    int ans=0;
    for(int i=20;i>=0;i--)
        if(dep[f[a][i]]>=dep[b])
        {
            ans=max(ans,g[a][i]);
            a=f[a][i];
        }
    if(a==b)    return ans;
    for(int i=20;i>=0;i--)
        if(f[a][i]!=f[b][i])
        {
            ans=max(ans,max(g[a][i],g[b][i]));
            a=f[a][i];b=f[b][i];
        }
    return max(ans,max(g[a][0],g[b][0]));
}

signed main()
{
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&ed[i].u,&ed[i].v,&ed[i].w);
    sort(ed+1,ed+1+m);
    for(int i=1;i<=n;i++)   fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int a=find(ed[i].u),b=find(ed[i].v);
        if(a==b)    continue;
        fa[a]=b;
        add(ed[i].u,ed[i].v,ed[i].w);
        add(ed[i].v,ed[i].u,ed[i].w);
    }

    dfs(1,0);

    for(int i=1;i<=q;i++)
    {
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        int lca=get_lca(a,b);
        if(lca>c)   printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}