最小树形图 Tarjan的DMST算法

前言
网上怎么都是朱刘算法啊？
那我来写一篇 Tarjan 的 DMST 算法吧 qwq
注：本文的DMST采用左偏树+并查集实现
时间复杂度为 O ( E + V log ⁡ E ) O(E+Vlog E) O(E+VlogE)
如果采用斐波那契堆则为 O ( E + V log ⁡ V ) O(E+Vlog V) O(E+VlogV)
由于差别不大（~~其实是q779不会斐波那契堆~~），因此本文不会提及
如果需要模板题数据的可以私信我（ qwq
文章目录
前言最小树形图
1.朱刘算法（Edmonds算法）2.Tarjan的DMST算法（Tarjan的优化算法）3.加强版模板题总结参考文献
最小树形图
模板题：P4716 【模板】最小树形图
题目描述

给定包含 n n n 个结点， m m m 条有向边的一个图。试求一棵以结点 r r r 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 r r r 为根的最小树形图，输出 − 1 -1 −1。
1.朱刘算法（Edmonds算法）
有向图上的最小生成树（Directed Minimum Spanning Tree）称为最小树形图。
常用的算法是朱刘算法（也称 Edmonds 算法），可以在 O ( n m ) O(nm) O(nm) 时间内解决最小树形图问题。
注意到有根最小树形图满足从根结点可以到达任意结点的性质
算法流程：
求出图中的最短弧集合 E 0 E_0 E0若 E 0 E_0 E0 中存在环，则对图进行缩点和重构，包括边权的修改和点的处理，转到步骤1若 E 0 E_0 E0 中不存在环，则展开收缩点，即求得最小树形图，算法结束。
对于环上结点 v v v 的入边，因为选择了一条这样的边相当于删除了一条环边
所以将边权设为 w − ine[v] w-text{ine[v]} w−ine[v]，其中 ine[v] text{ine[v]} ine[v] 表示结点 v v v 的最短弧（权值最小的入边）
本文不过多叙述朱刘算法，仅给出代码
#include 
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++;
}
templatevoid 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;
}
templatevoid 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 
可以发现这就是个暴力 qwq 
 
2.Tarjan的DMST算法（Tarjan的优化算法） 
观察朱刘算法的实现 
 
 算法流程： 
 求出图中的最短弧集合 
      
       
        
         
          
           E
          
          
           0
          
         
        
        
         E_0
        
       
      E0若 
      
       
        
         
          
           E
          
          
           0
          
         
        
        
         E_0
        
       
      E0 中存在环，则对图进行缩点和重构，包括边权的修改和点的处理，转到步骤1若 
      
       
        
         
          
           E
          
          
           0
          
         
        
        
         E_0
        
       
      E0 中不存在环，则展开收缩点，即求得最小树形图，算法结束。 
 
可以发现这是三种操作 
查询最小值整体减去一个数合并若干集合 
1,3操作可以通过左偏树（可并堆）直接维护 
2操作可以通过在左偏树上设懒标记实现 
朱刘算法每次需要判断是否存在环，很慢 
于是我们尝试直接将原图缩成一个点（尽管实现的时候并不完全如此） 
然而原图不一定是强连通图，不过我们只要通过添加 
    
     
      
       
        n
       
      
      
       n
      
     
    n 条边权为 
    
     
      
       
        +
       
       
        ∞
       
      
      
       +infty
      
     
    +∞ 就可以让它强连通了 
形象地描述，如果我们最后“迫不得已”选择了这些额外的边，则原图不存在最小树形图 
本质上该算法就是不断将最短弧加入当前的最小树形图 
当树形图中出现环时将环进行缩点处理 
算法实现： 
我们可以维护一个栈，每次将栈顶元素 
    
     
      
       
        v
       
      
      
       v
      
     
    v 的最短弧的起点 
    
     
      
       
        u
       
      
      
       u
      
     
    u 入栈 
如果 
    
     
      
       
        u
       
      
      
       u
      
     
    u 已经在栈中，则出现了环，将环进行缩点即可 
注意如果计算答案时存在根节点 
    
     
      
       
        r
       
      
      
       r
      
     
    r 的入边，显然不可计入答案 
引理：下文代码中，建树时间复杂度为 
    
     
      
       
        O
       
       
        (
       
       
        m
       
       
        )
       
      
      
       O(m)
      
     
    O(m) 
 
 证明： 
 对于结点 
     
      
       
        
         k
        
       
       
        k
       
      
     k ，设其共有 
     
      
       
        
         
          d
         
         
          k
         
        
       
       
        d_k
       
      
     dk 条入边的 
 对于第 
     
      
       
        
         i
        
       
       
        i
       
      
     i 轮合并，需合并 
     
      
       
        
         
          
           
            d
           
           
            k
           
          
          
           
            2
           
           
            i
           
          
         
        
       
       
        dfrac{d_k}{2^i}
       
      
     2idk 次，且该轮合并左偏树上各有 
     
      
       
        
         i
        
       
       
        i
       
      
     i 个结点 
 则复杂度为
 
      
       
        
         
          O
         
         
          
           (
          
          
           
            ∑
           
           
            
             i
            
            
             =
            
            
             1
            
           
           
            
             
              
               log
              
              
               ⁡
              
             
             
              2
             
            
            
             
              d
             
             
              k
             
            
           
          
          
           
            
             
              d
             
             
              k
             
            
            
             
              2
             
             
              i
             
            
           
           
            ×
           
           
            
             (
            
            
             2
            
            
             
              
               log
              
              
               ⁡
              
             
             
              2
             
            
            
             i
            
            
             +
            
            
             1
            
            
             )
            
           
          
          
           )
          
         
         
          =
         
         
          O
         
         
          (
         
         
          
           d
          
          
           k
          
         
         
          )
         
        
        
          Oleft(sumlimits_{i=1}^{log_2 d_k}{dfrac{d_k}{2^i}times left(2log_2{i} + 1right)}right) = O(d_k) 
        
       
      O⎝⎛i=1∑log2dk2idk×(2log2i+1)⎠⎞=O(dk)
 
     
      
       
        
         ∵
        
        
         ∑
        
        
         
          d
         
         
          k
         
        
        
         =
        
        
         m
        
       
       
        because sum d_k = m
       
      
     ∵∑dk=m 
 
     
      
       
        
         ∴
        
       
       
        therefore
       
      
     ∴ 总复杂度为
 
      
       
        
         
          O
         
         
          
           (
          
          
           
            ∑
           
           
            
             d
            
            
             k
            
           
          
          
           
            ∑
           
           
            
             i
            
            
             =
            
            
             1
            
           
           
            
             
              
               log
              
              
               ⁡
              
             
             
              2
             
            
            
             
              d
             
             
              k
             
            
           
          
          
           
            
             
              d
             
             
              k
             
            
            
             
              2
             
             
              i
             
            
           
           
            ×
           
           
            
             (
            
            
             2
            
            
             
              
               log
              
              
               ⁡
              
             
             
              2
             
            
            
             i
            
            
             +
            
            
             1
            
            
             )
            
           
          
          
           )
          
         
         
          =
         
         
          O
         
         
          (
         
         
          m
         
         
          )
         
        
        
          Oleft(sum_{d_k}sumlimits_{i=1}^{log_2 d_k}{dfrac{d_k}{2^i}times left(2log_2{i} + 1right)}right) = O(m) 
        
       
      O⎝⎛dk∑i=1∑log2dk2idk×(2log2i+1)⎠⎞=O(m)
 证毕 。 
 
时间复杂度为 
    
     
      
       
        O
       
       
        (
       
       
        m
       
       
        +
       
       
        n
       
       
        log
       
       
        ⁡
       
       
        m
       
       
        )
       
      
      
       O(m+nlog m)
      
     
    O(m+nlogm) 
 
 证明： 
 由引理可知，建树复杂度为 
     
      
       
        
         O
        
        
         (
        
        
         m
        
        
         )
        
       
       
        O(m)
       
      
     O(m) 
 因为每个结点至多入栈一次，每次查询最短弧复杂度为 
     
      
       
        
         O
        
        
         (
        
        
         log
        
        
         ⁡
        
        
         m
        
        
         )
        
       
       
        O(log m)
       
      
     O(logm) 
 则总复杂度为 
     
      
       
        
         O
        
        
         (
        
        
         m
        
        
         +
        
        
         n
        
        
         log
        
        
         ⁡
        
        
         m
        
        
         )
        
       
       
        O(m+nlog m)
       
      
     O(m+nlogm) 
 证毕。 
 
代码如下 
#include 
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++;
}
templatevoid 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;
}
templatevoid 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 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 
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++;
}
templatevoid 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;
}
templatevoid 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 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] 左偏树简介 
转载请说明出处
最小树形图 Tarjan的DMST算法

C/C++/C#相关栏目本月热门文章
