嘘~ 正在从服务器偷取页面 . . .

最小树形图 Tarjan的DMST算法

算法 数据结构
OI
发布日期:   2022-03-27
更新日期:   2022-07-26
文章字数:   3k

最小树形图 Tarjan的DMST算法

前言

网上怎么都是朱刘算法啊？

那我来写一篇 Tarjan 的 DMST 算法吧 qwq

注：本文的DMST采用左偏树+并查集实现

时间复杂度为 \(O(E+V\log E)\)

如果采用斐波那契堆则为 \(O(E+V\log V)\)

由于差别不大（其实是q779不会斐波那契堆），因此本文不会提及

如果需要模板题数据的可以私信我（ qwq

最小树形图

模板题：P4716 【模板】最小树形图

题目描述

给定包含 \(n\) 个结点， \(m\) 条有向边的一个图。试求一棵以结点 \(r\) 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 \(r\) 为根的最小树形图，输出 \(-1\)。

1.朱刘算法（Edmonds算法）

有向图上的最小生成树（Directed Minimum Spanning Tree）称为最小树形图。

常用的算法是朱刘算法（也称 Edmonds 算法），可以在 \(O(nm)\) 时间内解决最小树形图问题。

注意到有根最小树形图满足从根结点可以到达任意结点的性质

算法流程：

  1. 求出图中的最短弧集合 \(E_0\)
  2. 若 \(E_0\) 中存在环，则对图进行缩点和重构，包括边权的修改和点的处理，转到步骤1
  3. 若 \(E_0\) 中不存在环，则展开收缩点，即求得最小树形图，算法结束。

对于环上结点 \(v\) 的入边，因为选择了一条这样的边相当于删除了一条环边

所以将边权设为 \(w-\text{ine[v]}\)，其中 \(\text{ine[v]}\) 表示结点 \(v\) 的最短弧（权值最小的入边）

本文不过多叙述朱刘算法，仅给出代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
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('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define M (int)(1e4+15)
#define N (int)(1e3+5)
struct Edge
{
    int u,v,w,next;
}e[M];
int n,m,rt;
int pre[N],ine[N];
int vis[N],id[N];
int pos=1,head[N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
int solve()
{
    int ans=0;
    while(1)
    {
        for(int i=1; i<=n; i++)
            ine[i]=INF;
        for(int i=2; i<=pos; i++)
        {
            int u=e[i].u,v=e[i].v;
            if(u!=v&&e[i].w<ine[v])
                ine[v]=e[i].w,pre[v]=u;
        }
        for(int i=1; i<=n; i++)
            if(i!=rt&&ine[i]==INF)return INF;
        int cnt=0;
        for(int i=1; i<=n; i++)
            vis[i]=id[i]=0;
        for(int i=1; i<=n; i++)
        {
            if(i==rt)continue;
            ans+=ine[i];
            int v=i;
            while(vis[v]!=i&&!id[v]&&v!=rt)
            {
                vis[v]=i;
                v=pre[v];
            }
            if(!id[v]&&v!=rt)
            {
                id[v]=++cnt;
                for(int u=pre[v]; u!=v; u=pre[u])
                    id[u]=cnt;
            }
        }
        if(!cnt)break;
        for(int i=1; i<=n; i++)
            if(!id[i])id[i]=++cnt;
        for(int i=2; i<=pos; i++)
        {
            int u=e[i].u,v=e[i].v;
            e[i].u=id[u];e[i].v=id[v];
            if(id[u]!=id[v])e[i].w-=ine[v];
        }
        rt=id[rt];
        n=cnt;
    }
    return ans;
}
signed main()
{
    read(n);read(m);read(rt);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        addEdge(u,v,w);
    }
    int res=solve();
    write(res==INF?-1:res);pc('\n');
    return 0;
}

可以发现这就是个暴力 qwq

2.Tarjan的DMST算法（Tarjan的优化算法）

观察朱刘算法的实现

算法流程：

  1. 求出图中的最短弧集合 \(E_0\)
  2. 若 \(E_0\) 中存在环，则对图进行缩点和重构，包括边权的修改和点的处理，转到步骤1
  3. 若 \(E_0\) 中不存在环，则展开收缩点，即求得最小树形图，算法结束。

可以发现这是三种操作

  1. 查询最小值
  2. 整体减去一个数
  3. 合并若干集合

1,3操作可以通过左偏树（可并堆）直接维护

2操作可以通过在左偏树上设懒标记实现

朱刘算法每次需要判断是否存在环，很慢

于是我们尝试直接将原图缩成一个点（尽管实现的时候并不完全如此）

然而原图不一定是强连通图，不过我们只要通过添加 \(n\) 条边权为 \(+\infty\) 就可以让它强连通了

形象地描述，如果我们最后“迫不得已”选择了这些额外的边，则原图不存在最小树形图

本质上该算法就是不断将最短弧加入当前的最小树形图

当树形图中出现环时将环进行缩点处理

算法实现：

我们可以维护一个栈，每次将栈顶元素 \(v\) 的最短弧的起点 \(u\) 入栈

如果 \(u\) 已经在栈中，则出现了环，将环进行缩点即可

注意如果计算答案时存在根节点 \(r\) 的入边，显然不可计入答案

引理：下文代码中，建树时间复杂度为 \(O(m)\)

证明：

对于结点 \(k\) ，设其共有 \(d_k\) 条入边的

对于第 \(i\) 轮合并，需合并 \(\dfrac{d_k}{2^i}\) 次，且该轮合并左偏树上各有 \(i\) 个结点

则复杂度为 \[ O\left(\sum\limits_{i=1}^{\log_2 d_k}{\dfrac{d_k}{2^i}\times \left(2\log_2{i} + 1\right)}\right) = O(d_k) \] \(\because \sum d_k = m\)

\(\therefore\) 总复杂度为 \[ O\left(\sum_{d_k}\sum\limits_{i=1}^{\log_2 d_k}{\dfrac{d_k}{2^i}\times \left(2\log_2{i} + 1\right)}\right) = O(m) \] 证毕 。

时间复杂度为 \(O(m+n\log m)\)

证明：

由引理可知，建树复杂度为 \(O(m)\)

因为每个结点至多入栈一次，每次查询最短弧复杂度为 \(O(\log m)\)

则总复杂度为 \(O(m+n\log m)\)

证毕。

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
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('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e3+15)
#define M (int)(2e4+15)
// 全部两倍
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
int n,m,r,cnt,f[N];
int vis[N];
int stk[N],top;
queue<int> q[N];
namespace leftist
{
    struct node
    {
        int ch[2],u,v,w,dist,tag;
    }t[M];
    int tot,rt[M];
    int New(int u,int v,int w)
    {
        t[++tot]={0,0,u,v,w};
        return tot;
    }
    void push_down(int x)
    {
        t[ls(x)].tag+=t[x].tag;
        t[ls(x)].w+=t[x].tag;
        t[rs(x)].tag+=t[x].tag;
        t[rs(x)].w+=t[x].tag;
        t[x].tag=0;
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x|y;
        push_down(x);push_down(y);
        if(t[x].w>t[y].w)swap(x,y);
        rs(x)=merge(rs(x),y);
        if(t[rs(x)].dist>t[ls(x)].dist)
            swap(ls(x),rs(x));
        t[x].dist=t[rs(x)].dist+1;
        return x;
    }
    int remove(int x)
    {
        push_down(x);
        return merge(ls(x),rs(x));
    }
    void build()
    {
        for(int i=1; i<=n; i++)
        {
            if(q[i].empty())continue;
            while(q[i].size()!=1)
            {
                int p1=q[i].front();q[i].pop();
                int p2=q[i].front();q[i].pop();
                p1=merge(p1,p2);
                q[i].push(p1);
            }
            if(!q[i].empty())
                rt[i]=merge(rt[i],q[i].front()),
                q[i].pop();
        }
    }
}
int find(int x)
{
    return f[x]==x?x:f[x]=find(f[x]);
}
signed main()
{
    using namespace leftist;
    read(n);read(m);read(r);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        int p=New(u,v,w);
        q[v].push(p);
        // rt[v]=merge(rt[v],p);
    }
    for(int i=1; i<=n; i++)
    {
        int p=New(i>1?i-1:n,i,INF);
        q[i].push(p);
        // rt[i]=merge(rt[i],p);
    }
    build();
    for(int i=1; i<=2*n; i++) f[i]=i;
    stk[++top]=r;vis[r]=1;
    int ans=0,cnt=n;
    while(rt[stk[top]])
    {
        int &p=rt[stk[top]];
        int u=find(t[p].u);
        if(u==stk[top])
        {
            p=remove(p);
            continue;
        }
        if(!vis[u])
        {
            stk[++top]=u;
            vis[u]=1;
            continue;
        }
        int q=++cnt;
        while(vis[u])
        {
            int v=stk[top--];
            vis[v]=0;f[v]=q;
            node *tmp=&t[rt[v]];
            tmp->tag-=tmp->w;
            if(find(tmp->v)!=find(r))ans+=tmp->w;
            rt[v]=remove(rt[v]);
            rt[q]=merge(rt[q],rt[v]);
        }
        stk[++top]=q;
        vis[q]=1;
    }
    ans=ans>=INF?-1:ans;
    write(ans);pc('\n');
    return 0;
}

3.加强版模板题

这里有一道我写的模板题

可以卡掉暴力朱刘算法

大家可以在这里调试代码

题目链接：U210116 【模板】最小树形图（加强版）

这里是std

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1=buf1,*p2=buf1;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
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('-');}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e5+15)
#define M (int)(2e6+15)
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
int n,m,r,cnt,f[N];
int vis[N],stk[N],top;
queue<int> q[N];
namespace leftist
{
    struct node
    {
        int ch[2],u,v,w,dist,tag;
    }t[M];
    int tot,rt[M];
    int New(int u,int v,int w)
    {
        t[++tot]={0,0,u,v,w};
        return tot;
    }
    void push_down(int x)
    {
        t[ls(x)].tag+=t[x].tag;
        t[ls(x)].w+=t[x].tag;
        t[rs(x)].tag+=t[x].tag;
        t[rs(x)].w+=t[x].tag;
        t[x].tag=0;
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x|y;
        push_down(x);push_down(y);
        if(t[x].w>t[y].w)swap(x,y);
        rs(x)=merge(rs(x),y);
        if(t[rs(x)].dist>t[ls(x)].dist)
            swap(ls(x),rs(x));
        t[x].dist=t[rs(x)].dist+1;
        return x;
    }
    int remove(int x)
    {
        push_down(x);
        return merge(ls(x),rs(x));
    }
    void build()
    {
        for(int i=1; i<=n; i++)
        {
            if(q[i].empty())continue;
            while(q[i].size()!=1)
            {
                int p1=q[i].front();q[i].pop();
                int p2=q[i].front();q[i].pop();
                p1=merge(p1,p2);
                q[i].push(p1);
            }
            if(!q[i].empty())
            {
                rt[i]=merge(rt[i],q[i].front());
                q[i].pop();
            }
        }
    }
}
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}
// double BEGIN_CLOCK,END_CLOCK;
signed main()
{
	// freopen("2.in","r",stdin);
	// freopen("2.out","w",stdout);
	// ofstream outfile;
    // outfile << fixed << setprecision(4);
    // outfile.open("check.txt");
    // // outfile << fixed;
    // BEGIN_CLOCK=clock();
    using namespace leftist;
    read(n);read(m);read(r);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        int p=New(u,v,w);
        q[v].push(p);
        // rt[v]=merge(rt[v],p);
    }
    for(int i=1; i<=n; i++)
    {
        int p=New(i>1?i-1:n,i,INF);
        q[i].push(p);
        // rt[i]=merge(rt[i],p);
    }
    build();
    for(int i=1; i<=2*n; i++)f[i]=i;
    stk[++top]=r;vis[r]=1;
    int ans=0,cnt=n;
    while(rt[stk[top]])
    {
		if(ans>=INF)
			return puts("-1"),0;
        int &p=rt[stk[top]];
        int u=find(t[p].u);
        if(u==stk[top])
        {
            p=remove(p);
            continue;
        }
        if(!vis[u])
        {
            stk[++top]=u;
            vis[u]=1;
            continue;
        }
        int q=++cnt;
        while(vis[u])
        {
            int v=stk[top--];
            vis[v]=0;f[v]=q;
            node *tmp=&t[rt[v]];
            tmp->tag-=tmp->w;
            if(find(tmp->v)!=find(r))
                ans+=tmp->w;
            rt[v]=remove(rt[v]);
            rt[q]=merge(rt[q],rt[v]);
        }
        stk[++top]=q;
        vis[q]=1;
    }
    write(ans);pc('\n');
	// END_CLOCK=clock();
    // outfile << "运行时间: " << (double)((END_CLOCK-BEGIN_CLOCK)/CLOCKS_PER_SEC) << "s" << endl;
    // outfile.close();
    return 0;
}

总结

本文简单介绍了Tarjan的DMST算法及左偏树实现方法

参考文献

[1] OI Wiki 最小树形图

[2] CHiCO的博客 题解 P4716

[3] 左偏树简介

文章作者: q779
文章链接: https://q779.cn/2022/03/27/zui-xiao-shu-xing-tu-tarjan-de-dmst-suan-fa/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 q779 !
算法 数据结构
评论
  目录