洛谷P4234 最小差值生成树 题解

题目链接：P4234 最小差值生成树

题意：给定一个点标号从 1 1 1 到 n n n 的、有 m m m 条边的无向图，求边权最大值与最小值的差值最小的生成树，图可能存在自环

这个题不太好利用kruskal来维护（其实kruskal来做就是暴力枚举）

考虑使用LCT动态维护生成树

可以先回顾一下如何用LCT来求解最小生成树 link

因为边之间没有什么本质区别，我们可以先把边按大小排序，以保证编号越小的边点，权值越小

然后我们可以从小到大枚举生成树中的最大值（从大到小其实是类似的）

那么我们只要保证生成树中边权的最小值尽可能的大即可

也就是说，在枚举最大边的时候，如果两结点未连通，我们可以直接将这两点连接

如果已经连通，那么就将当前生成树中x,y所成的链中的最小边扔掉，然后用最大边连接这两点

显然这个最小值就是生成树中编号最小的那一个，而且随着枚举会单调不降，那我们可以整个变量记录它，而由于它的单调不降性质，寻找这个最小值是不会影响到复杂度的

对于已经不在生成树的边（包括构成自环和被更新掉的边），我们直接让那个维护最小值的变量跳过它就行了，具体可以看下面代码

时间复杂度 O ( m log ⁡ m ) O(m\log m) O(mlogm)

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(4e5+5)
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
int n,m,idx,ans=INF,cnt,d;
namespace LCT
{
    struct Edge{int u,v,w;}e[N];
    int cmp(Edge a,Edge b){return a.w<b.w;}
    struct node
    {
        int ch[2],id,fa,tag,vis;
    }t[N];
    #define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x))
    void pushr(int x)
    {
        swap(t[x].ch[0],t[x].ch[1]);
        t[x].tag^=1;
    }
    void push_up(int x)
    {
        t[x].id=x;
        if(t[t[x].ch[0]].id>n&&(t[x].id<=n||t[x].id>t[t[x].ch[0]].id))
            t[x].id=t[t[x].ch[0]].id;
        if(t[t[x].ch[1]].id>n&&(t[x].id<=n||t[x].id>t[t[x].ch[1]].id))
            t[x].id=t[t[x].ch[1]].id;
    }
    void push_down(int x)
    {
        if(t[x].tag)
        {
            if(t[x].ch[0])pushr(t[x].ch[0]);
            if(t[x].ch[1])pushr(t[x].ch[1]);
            t[x].tag=0;
        }
    }
    void push_all(int x)
    {
        if(!isroot(x))push_all(t[x].fa);
        push_down(x);
    }
    void rotate(int x)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        int k=t[y].ch[1]==x;
        if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;
        t[x].fa=z;
        t[y].ch[k]=t[x].ch[k^1];
        t[t[x].ch[k^1]].fa=y;
        t[x].ch[k^1]=y;
        t[y].fa=x;
        push_up(y);
        push_up(x);
    }
    void splay(int x)
    {
        push_all(x);
        while(!isroot(x))
        {
            int y=t[x].fa;
            int z=t[y].fa;
            if(!isroot(y))
            (t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
            rotate(x);
        }
    }
    void access(int x)
    {
        for(int y=0;x;y=x,x=t[x].fa)
            splay(x),t[x].ch[1]=y,push_up(x);
    }
    void make_root(int x)
    {
        access(x);splay(x);
        pushr(x);
    }
    int find_root(int x)
    {
        access(x);splay(x);
        while(t[x].ch[0])push_down(x),x=t[x].ch[0];
        splay(x);
        return x;
    }
    void split(int x,int y)
    {
        make_root(x);
        access(y);splay(y);
    }
    void link(int x,int y)
    {
        make_root(x);
        if(find_root(y)!=x)t[x].fa=y;
    }
    /*
    void cut(int x,int y)
    {
        make_root(x);
        if(find_root(y)==x&&t[y].fa==x&&!t[y].ch[0])
        {
            t[x].ch[1]=t[y].fa=0;
            push_up(x);
        }
    }
    */
    int ck(int x,int y)
    {
        make_root(x);
        return find_root(y)!=x;
    }
}
signed main()
{
    using namespace LCT;
    read(n);read(m);
    for(int i=1; i<=m; i++)
    {
        read(e[i].u);read(e[i].v);
        read(e[i].w);
    }
    sort(e+1,e+1+m,cmp);d=1;
    for(int i=1; i<=m; i++)
    {
        int idx=n+i,w=e[i].w,x=e[i].u,y=e[i].v;
        if(x==y){t[idx].vis=1;continue;}
        if(ck(x,y))
            link(x,idx),link(idx,y),++cnt;
        else
        {
            split(x,y);int now=t[y].id;
            t[now].vis=1;splay(now);
            t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;
            link(x,idx);link(idx,y);
        }
        while(t[d+n].vis&&d<i)++d;
        if(cnt>=n-1)ans=min(ans,w-e[d].w);
    }
    write(ans);pc('\n');
    return 0;
}

顺便贴一下kruskal的暴力代码吧 时间复杂度是 O ( m 2 ) O(m^2) O(m2) 的

这道题数据水过头了所以暴力也能过（已经反馈了

注：这个暴力是我去年(2021.2.6)写的，所以码风区别较大（（

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define R register
int n,m,t,head[50005],in[50005],ans=INT_MAX,pos=1,cnt;
int f[50005],a[50005];
struct Edge
{
    int u,v,w,next;
    const bool operator<(const Edge &o)const
    {
        return w<o.w;
    }
}e[500005];
void init()
{
    for(R int i=1; i<=n; i++)
        f[i]=i;
    cnt=0;
}
void add(R int u,R int v,R int w)
{
    e[pos]={u,v,w,head[u]};
    head[u]=pos++;
}
int find(R int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(R int i=1,u,v,w; i<=m; i++)
    {
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
    }
    if(m==0)return puts("-1"),0;
    sort(e+1,e+pos+1);
    for(R int k=1; k<=pos; k++)
    {
        if(k>1&&e[k].w==e[k-1].w)continue;
        init();
        for(R int i=k;i<=pos; i++)
        {
            R int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
            if(u==v)continue;
            f[u]=v;
            if(++cnt==n-1)
            {
                if(ans>e[i].w-e[k].w)ans=e[i].w-e[k].w;
                break;
            }
        }
        if(cnt!=n-1)break;
    }
    printf("%lld\n",ans);
    return 0;
}

转载请说明出处