初识 朱刘算法

发表于 | 分类于 | 阅读次数:
字数统计: 1,280 字

又到了每周一次的实验室算法专题分享，这次讲的是的是朱刘算法（好奇葩的算法名字），朱刘算法主要用来解决的是最小树型图的问题，算法整体的理解不是很难结合模板代码比较容易理解。接下来讲讲我的理解吧，当做自己学习的一个总结吧！

最小树型图

我们知道最小生成树是一个加权无向图，有n-1条边，能够连接图中所有的点的边集。这里的最小树型图就是最小生成树的有向图版本。除了根节点之外所有的节点都有一条入边指向它。

朱刘算法

概述

首先我们可以利用贪心思想，像Kruscal算法的选边原则一样，我们可以先找到每个节点的入边中最小的一条边，如果选出来的这些边中不能构成环，这样选出来的边就组成了一个最小树型图。但很多时候我们选出来的边是含有环的，对于环的处理，朱刘算法采取的不是直接换边，而是用一个点来代替原来的那个环（这个操作叫做缩点操作），并且修改跟这个环里的点有关的边的权值 ， 为什么要修改权值呢？因为我们是换边 ， 不是增加边 ， 当我们每更换一个点的入边的时候我们就要去掉原来那个入边 ， 于是我们把这个点所有可能的入边全部减小原来我们枚举的那个边的权值 ， 这样每增加一条入边无形中就删去了原来那条边(此处想通再继续)。 当我们把所有的环都缩点并且修改权值之后 ， 相当于就重新建图了。

算法步骤

算法用到必要数组有inw[]用来计算每个点的最小入边权值，id[]用来记录重新构图以后对应的点的编号，pre[]数组记录最小入边的上一个点

  • 初始化inw数组和pre数组，找到每个点的最小入边
  • 寻找图中的环，通过一个辅助的数组v数组来实现
  • 进行缩点操作，将一个环中的点当做一个点
  • 重新构图

POJ 3164

题意

给出N个点、这N个点的坐标信息和这N个点的M条关联关系，求最小树型图的权值代价和

题解

裸的朱刘算法，模板题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

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

#define in(a) scanf("%d",&a)

using namespace std;
const int maxn=110;
#define INF 0x3f3f3f3f

struct edge
{
    int u,v;
    double  w;
    edge(int uu,int vv, double ww):u(uu),v(vv),w(ww){}
};

vector<edge> g;

int id[maxn],pre[maxn],v[maxn];
double inw[maxn],ans;
int n,m;
int xx[maxn],yy[maxn];

double getdis(int a,int b)
{
    double ret= sqrt(double((yy[b]-yy[a])*(yy[b]-yy[a])+(xx[b]-xx[a])*(xx[b]-xx[a])));
    return ret;
}

bool fun(int s)      //存在最小树型图时，返回TRUE，ans；不存在的时候，返回FALSE
{
    ans=0;
    while (true)
    {

        for(int i=0;i<=n;i++)
        {
            inw[i]=INF;
            id[i]=-1;
            v[i]=-1;
            pre[i]=-1;
        }
        //找到每个点的最小入边
        for(int i=0;i<g.size();i++)
            if(g[i].w <=inw[g[i].v] && g[i].v!=g[i].u)
            {
                inw[g[i].v]=g[i].w;
                pre[g[i].v]=g[i].u;
            }
        pre[s]=s;
        inw[s]=0;       //根节点没有入边
        //计算总的权重和
        for(int i=1;i<=n;i++)
        {
            if(inw[i]==INF)
                return false;     //没有找到最小的入边的时候，返回错误
            ans+=inw[i];
        }
        //判断有没有环
        int idx=1;
        for(int i=1;i<=n;i++)
        {
            if(v[i]==-1)     //v[]作用是判断有没有环
            {
                int t=i;
                while (v[t]==-1)
                {
                    v[t]=i;
                    t=pre[t];
                }
                if(v[t]!=i || t==s)
                    continue;      //没有环的时候
                id[t]=idx++;      //重构图中新的点
                for(int j=pre[t];j!=t;j=pre[j])id[j]=idx-1;     //缩点操作，确定前后点的关系
            }
        }
        if(idx==1)
            return true;
        //为不在环中的点建立图之间点的关系
        for(int i=1;i<=n;i++)
            if(id[i]==-1)id[i]=idx++;
        //重新构图,改变边连接的两个点的关系
        for(int i=0;i<g.size();i++)
        {
            g[i].w-=inw[g[i].v];
            g[i].u=id[g[i].u];
            g[i].v=id[g[i].v];
        }
        n=idx-1;
        s=id[s];
    }
}

void solve()
{
    while (scanf("%d %d",&n,&m)!=EOF)
    {
        g.clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&xx[i],&yy[i]);
        }
        int a,b;
        double we;
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&a,&b);
            we=getdis(a,b);
            g.push_back(edge(a,b,we));
        }
        if(fun(1))
            printf("%.2lf\n",ans);
        else
            printf("poor snoopy\n");
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    solve();
    return 0;
}