最小树形图构造(朱刘算法)学习笔记

什么是最小树形图

最小树形图就是给定一个$n$个点的有向图,我们钦定一个根,现在要找$n-1$条边,在根能到达其他所有点的前提条件下,使得$n-1$条边的总长度尽可能小。


怎么找最小树形图

这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然,还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了,并学不会

图出自这里
image

上面这张图很好的诠释了朱刘算法的主要内容:
我们算法主要有以下几个步骤:
1. 找到到达每个点的长度最小的入边(根节点不找)
2. 这些边如果连成一颗树则结束;
3. 如果这些边中除了根节点以外有孤独一个的点的话,则无解;
4. 否则一定会连出一些环,我们把这些环缩起来,答案加上这些环上边权和,然后构建新图:所有连向这些环的边的边权减去对应的点之前的最小的入边的边权(即步骤1找到的那一条)。建完新图之后回到步骤1。


朱刘算法如何实现

从上面的口胡,我们可以发现,我们要实现一个动态缩点,动态构图的过程。可想而知,算法并不好写。

笔者个人的写法是开两个图,辗转使用。魔改Tarjan来实现找环的过程。
代码在这里(丑不忍赌)

//Luogu P4716 【模板】最小树形图
//Apr,9th,2019
//朱刘算法求有向图最小生成树
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=2*100+10;
const int inf=0x3f3f3f3f;
struct edge
{
    int t,w;
    edge (int x=0,int y=0)
    {
        t=x,w=y;
    }
};
vector <edge> e[2][N];
edge e2[N];
int n,m,r,id[N],cnt,t_now;
bool vis[N],gone[N],IsNew[N];
int mstack[N],top;
int dfs(int now)
{
    int t_ans=0;
    mstack[++top]=now;
    vis[now]=gone[now]=true;
    if(vis[e2[now].t]==true)
    {
        cnt++;
        while(mstack[top+1]!=e2[now].t)
            IsNew[mstack[top]]=true,
            id[mstack[top--]]=cnt;
        t_ans+=e2[now].w;
    }
    else if(gone[e2[now].t]==false)
    {
        t_ans=dfs(e2[now].t);
        if(id[now]==cnt)
            t_ans+=e2[now].w;
    }
    vis[now]=false;
    return t_ans;
}
int GetID(int x)
{
    if(id[x]==0) return x;
    return id[x]=GetID(id[x]);
}
int ZhuLiu(int S)
{
    int ans=0;
    while(1)
    {
        for(int i=1;i<=n;i++)
            e2[GetID(i)].w=inf;
        for(int i=1;i<=cnt;i++)
            for(int j=0;j<int(e[t_now][i].size());j++)
                if(e[t_now][i][j].t!=S and e[t_now][i][j].w<e2[e[t_now][i][j].t].w)
                    e2[e[t_now][i][j].t].t=i,
                    e2[e[t_now][i][j].t].w=e[t_now][i][j].w;
        for(int i=1;i<=n;i++)
            if(i!=S and e2[GetID(i)].w==inf)
                return -1;//有单独点
        memset(gone,0,sizeof gone);
        memset(vis,0,sizeof vis);
        memset(IsNew,0,sizeof IsNew);
        int t_ans=0;
        for(int i=1;i<=n;i++)
            if(gone[GetID(i)]==false and i!=S)
                top=0,
                t_ans+=dfs(GetID(i)),gone[cnt]=true;
        ans+=t_ans;
        if(t_ans==0)
        {
            memset(vis,0,sizeof vis);
            bool OK=false;
            for(int i=1;i<=n;i++)
                if(i!=S and vis[GetID(i)]==false)
                    OK=max(OK,e2[GetID(i)].t==S),
                    ans+=e2[GetID(i)].w,vis[GetID(i)]=true;
            if(OK==false) ans=-1;
            break; //无环,完成
        }
        int mnext=(t_now+1)%2;
        for(int i=1;i<=cnt;i++)
            e[mnext][i].clear();
        for(int i=1;i<=cnt;i++)
            for(int j=0;j<int(e[t_now][i].size());j++)
                if(GetID(i)!=GetID(e[t_now][i][j].t))
                {
                    if(IsNew[e[t_now][i][j].t]==true)
                        e[mnext][GetID(i)].push_back(edge(GetID(e[t_now][i][j].t),e[t_now][i][j].w - e2[e[t_now][i][j].t].w));
                    else
                        e[mnext][GetID(i)].push_back(edge(GetID(e[t_now][i][j].t),e[t_now][i][j].w));
                }
        t_now=(t_now+1)%2;
    }
    return ans;
}
int main()
{
    freopen("4716.in","r",stdin);
    freopen("4716.out","w",stdout);

    n=read(),m=read(),r=read();
    for(int i=1;i<=m;i++)
    {
        int s=read(),t=read(),w=read();
        if(s==t) continue;
        e[t_now][s].push_back(edge(t,w));
    }

    cnt=n;
    int ans=ZhuLiu(r);

    printf("%d",ans);
    return 0;
}


朱刘算法的应用

目前好像只有模板题

点赞
  1. 456说道:
    Google Chrome 77.0.3865.120 Google Chrome 77.0.3865.120 Windows 10 x64 Edition Windows 10 x64 Edition

    你好

    1. Google Chrome 77.0.3865.120 Google Chrome 77.0.3865.120 Windows 10 x64 Edition Windows 10 x64 Edition

      你好呀 |´・ω・)ノ

发表评论

电子邮件地址不会被公开。必填项已用 * 标注