最小树形图(朱刘算法)

发表于   |   分类于

zhuliu

基本思想明白了点，代码还不大懂。。。
朱刘算法的大概过程如下：
1、找到除了root以为其他点的权值最小的入边。用in[i]记录
2、如果出现除了root以为存在其他孤立的点，则不存在最小树形图。
3、找到图中所有的环，并对环进行缩点，重新编号。
4、更新其他点到环上的点的距离，如：
环中的点有（Vk1，Vk2，… ，Vki）总共i个，用缩成的点叫Vk替代，则在压缩后的图中，其他所有不在环中点v到Vk的距离定义如下：
$gh[v][Vk]=min { gh[v][Vkj]-mincost[Vkj] } (1<=j<=i)$
而Vk到v的距离为$gh[Vk][v]=min { gh[Vkj][v] } (1<=j<=i)$
5、重复3，4知道没有环为止。

POJ 3164 Command Network

链接

Command Network

参考代码

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
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
typedef long long LL;
const int N=110;
const int M=10010;
const int INF=0x3f3f3f3f;
const double inf=1e10;
using namespace std;
struct node{
    int x,y;
}point[N];
struct edg {
    int u, v;
    double cost;
} edge[M];
int n, m;
int id[N],vis[N],pre[N];
double in[N];
double Directed_MST(int root) {
    double ret = 0;
    while(true) {
        for(int i=0;i<n;i++)
            in[i]=inf;
        for(int i=0;i<m;i++){    //找最小入边
            int u = edge[i].u;
            int v = edge[i].v;
            if(edge[i].cost < in[v] && u != v) {
                in[v] = edge[i].cost;
                pre[v] = u;
            }
        }
        for(int i=0;i<n;i++) { //如果存在除root以外的孤立点，则不存在最小树形图
            if(i == root)  continue;
            if(in[i] == inf)  return -1;
        }
        int cnt = 0;
        memset(vis,-1,sizeof(vis));
        memset(id,-1,sizeof(id));
        in[root] = 0;
        for(int i=0;i<n;i++) {    //找环
            ret += 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 v =edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            if(edge[i].u != edge[i].v)
                edge[i].cost -= in[v];
        }
        n = cnt;
        root = id[root];
    }
    return ret;
}
double distant(node a,node b)
{
    return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%d%d",&point[i].x,&point[i].y);
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            edge[i].u=a-1;
            edge[i].v=b-1;
            if(edge[i].u!=edge[i].v)
                edge[i].cost=distant(point[edge[i].u],point[edge[i].v]);
            else edge[i].cost=inf;
        }
        double ans=Directed_MST(0);
        if(ans==-1)
            printf("poor snoopy\n");
        else
            printf("%.2lf\n",ans);
    }
    return 0;
}