有向图的最小树形图(朱刘算法)

标签: dir_mst

最小树形图的定义:

设G=(V,E)是一个有向图,如果具有下述性质:

(1)G中不包含有向环

(2)存在一个顶点vi,它不是任何弧的终点,而V的其他顶点都恰好是唯一的一条弧的终点,则称G是以vi为根的树形图。

最小树形图就是有向图G=(V,E)中以vi为根的树形图中权值和最小的那个。显而易见,对于不同的vi,得到的最小树形图是不一样的,甚至有可能不存在。

1.基本算法

使用的是朱刘算法(Edmonds朱永津和刘振宏在1965年发表的)。下面都指定为根的顶点是v0

最小树形图基于贪心和缩点的思想。所谓缩点,就是将几个点看成是一个点,所有连到这几个点的边都视为连到收缩点,所有从这几个点连出的边都视为从收缩点连出。

(1)求最短弧集

从所有以vi(i≠0)为终点的弧中取一条最短的,若对于点vi,没有入边,则不存在最小树形图,算法结束;如果能取,则得到由n-1个点和n-1条边组成的图G的一个子图G',该子图的权值一定是最小的,但是不一定是一棵树。

(2)检查E0

若E0没有有向环且不含收缩点,则计算结束,E0就是G的以v0为根的最小树形图。若E0没有有向环,但含收缩点,则转步骤(4),若E0含有有向环C,则转入步骤(3)。

(3)把G中的C收缩成点u,对于图G中两端都属于C的边都被收缩掉了,其他弧仍保留,得到一个新的图G1,G1中以收缩点为终点的弧的长度要变化,变化的规律是:设点v在环C中,且环中指向v的边长为w,点v'不在环C中,则对于每一条边<v',v>,在G1中有边<v',u>与其对应,且权值WG1(<v',u>)=WG(<v',v>)-W。对于图G中以环C为起点的边<v',v>,在图G1中有边<u,v'>,则WG1(<u,v'>)=WG(<v,v'>)。需要注意的是,在此步生成的图G1中可能存在重边

对于图G和G1

1)如果图G1中没有以v0为根的最小树形图,则图G中也没有

2)如果图G1中有以v0为根的最小树形图,则可以按照步骤(4)中的展开方法得到图G中的最小树形图。

因此,此时需要将G1代入步骤(1)作为图G继续进行计算,反复计算直到图G1的最小树形图求出。

(4)展开收缩点

如果图G1的最小树形图T1已经求出,那么所有T1中的弧都属于T。将图G1的一个收缩点u展开成环C,从C中去掉与T1中弧有相同终点的弧,其他弧都属于T。

总结:求一个图G0的最小树形图,先求出最短弧集合E0。若E0不存在,则图G0的最小树形图不存在。若E0存在且不含有有向环,则E0就是T0中所有的边。如果E0存在且含有有向环,则收缩有向环成一个点u,并形成图G1,继续求G1的最小树形图直到图Gi,若图Gi无最小树形图,则图G0也不存在最小树形图,若图Gi有最小树形图Ti,则逐层展开得到T0.

在计算的过程中可以发现,图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和,在这条性质的影响下,如果不需要直到最终的T0中到底有哪几条边,只需知道T0的权值时,可以不需要展开。

时间复杂度分析:对于最小树形图的算法,最多会进行n-2次缩点,每次缩点以及边权修改的时间复杂度为O(n^2),所以,最小树形图的时间复杂度为O(n^3)。

对应例题:传送门

题解:跟据题目要求建图,然后就是朱刘算法的板子了

附上代码:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1005;

struct point{
    double x,y;
};
point p[maxn];

double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

struct node{
    int u,v;
    double len;
};
node edge[maxn*maxn];

int pre[maxn],id[maxn],vis[maxn];
double in[maxn];

double dir_mst(int root,int n,int m)
{
    double ans=0;
    while(1){
        for(int i=0;i<n;i++){
            in[i]=inf;
        }
        //找最短弧集
        for(int i=0;i<m;i++){
            int u=edge[i].u,v=edge[i].v;
            if(edge[i].len<in[v]&&u!=v){
                pre[v]=u;
                in[v]=edge[i].len;
            }
        }
        for(int i=0;i<n;i++){
            if(i==root){
                continue;
            }
            if(in[i]==inf){//如果某点入度为0,必定找不到
                return -1;
            }
        }
        //id为环的序号
        memset(id,-1,sizeof(id));
        memset(vis,-1,sizeof(vis));
        in[root]=0;
        int cnt=0;
        //找环
        for(int i=0;i<n;i++){
            ans+=in[i];
            int v=i;
            while(vis[v]!=i&&id[v]==-1&&v!=root){
                vis[v]=i;
                v=pre[v];
            }
            if(v!=root&&id[v]==-1){
                for(int u=pre[v];u!=v;u=pre[u]){
                    id[u]=cnt;
                }
                id[v]=cnt++;
            }
        }
        if(cnt==0){
            break;
        }
        for(int i=0;i<n;i++){
            if(id[i]==-1){
                id[i]=cnt++;
            }
        }
        //建立新图
        for(int i=0;i<m;i++){
            int u=edge[i].u,v=edge[i].v;
            edge[i].u=id[u];
            edge[i].v=id[v];
            if(id[u]!=id[v]){
                edge[i].len-=in[v];
            }
        }
        n=cnt;
        root=id[root];
    }
    return ans;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        for(int i=0;i<m;i++){
            scanf("%d%d",&edge[i].u,&edge[i].v);
            --edge[i].u;
            --edge[i].v;
            if(edge[i].u!=edge[i].v){
                edge[i].len=dis(p[edge[i].u],p[edge[i].v]);
            }else{
                edge[i].len=inf;
            }
        }
        double ans=dir_mst(0,n,m);
        if(ans==-1){
            printf("poor snoopy\n");
        }else{
            printf("%.2f\n",ans);
        }
    }
    return 0;
}

 

原文链接:加载失败,请重新获取