poj 3164 最小树形图朱刘算法

最小树形图，就是给有向带权图中指定一个特殊的点root，求一棵以root为根的有向生成树T，并且T中所有边的总权值最小。最小树形图的第一个算法是 1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。

(无向图的最小生成树即最小树形图，可用Prim’s Algorithm、Kruskal’s Algorithm等算法求。)

判断是否存在树形图的方法很简单，只需要以v为根作一次图的遍历就可以了。

步骤：

除根外每个点选最小入边（贪心）
检查环，每个点留一条入边，那么此时图中就有n-1条边，如果有环必定有点之间没有被连接。如果没有环同时每个结点（除根外）都有前驱，算法结束。
缩环成点，所有环上的所有的点（注意这些点每次循环都会被更新，是动态的），除了它的最小入边，其他的入边的权值都减去最小入边的权值，然后箭头指向“新”的点（也就是这个环）。

对于无固定根最小树形图，只要虚拟一个根连接所有点，权为边权总和+1,最后的结果减去（边权+1）即可。

  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


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

using namespace std;

const int VN=110;
const int INF=99999999;

double map[VN][VN];
int n,m,vis[VN],pt[VN][2],pre[VN];

double Cal(int i,int j){
    return sqrt(pow(pt[i][0]-pt[j][0],2.0)+pow(pt[i][1]-pt[j][1],2.0));
}

void DFS(int u){
    vis[u]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i] && map[u][i]!=INF)
            DFS(i);
}

bool Connected(){   //判断是否连通，如果连通一定存在最小树形图。 
    memset(vis,0,sizeof(vis));
    DFS(1);
    for(int i=1;i<=n;i++)
        if(!vis[i])
            return 0;
    return 1;
}

double ZLEmonds(){
    int i,j,k;
    bool circle[VN];
    double ans=0;
    memset(circle,0,sizeof(circle));
    while(1){
        for(i=2;i<=n;i++){  //找出最短弧集合E0 
            if(circle[i])
                continue;
            pre[i]=i;
            map[i][i]=INF;
            for(j=1;j<=n;j++){
                if(circle[j])
                    continue;
                if(map[j][i]<map[pre[i]][i])
                    pre[i]=j;
            }
        }
        for(i=2;i<=n;i++){
            if(circle[i])
                continue;
            j=i;
            memset(vis,0,sizeof(vis));
            while(!vis[j] && j!=1){
                vis[j]=1;
                j=pre[j];
            }
            if(j==1)    //检查是否有环，能找到根节点说明没环 
                continue;
            i=j;
            ans+=map[pre[i]][i];
            for(j=pre[i];j!=i;j=pre[j]){    //i不用标记，用作后面缩点用  
                ans+=map[pre[j]][j];
                circle[j]=1;
            }
            for(j=1;j<=n;j++){
                if(circle[j])
                    continue;
                if(map[j][i]!=INF)
                    map[j][i]-=map[pre[i]][i];
            }
            for(j=pre[i];j!=i;j=pre[j]) //将环中所有的点成点i，改变边 
                for(k=1;k<=n;k++){
                    if(circle[k])
                        continue;
                    map[i][k]=min(map[i][k],map[j][k]);
                    if(map[k][j]!=INF)
                        map[k][i]=min(map[k][i],map[k][j]-map[pre[j]][j]);
                }
            break;
        }
        if(i>n){    //求出最小树形图的权值 
            for(j=2;j<=n;j++){
                if(circle[j])
                    continue;
                ans+=map[pre[j]][j];
            }
            break;
        }
    }
    return ans;
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        int i,j;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                map[i][j]=INF;
        for(i=1;i<=n;i++)
            scanf("%d%d",&pt[i][0],&pt[i][1]);
        while(m--){
            scanf("%d%d",&i,&j);
            map[i][j]=Cal(i,j);
        }
        if(!Connected())
            printf("poor snoopy\n");
        else
            printf("%.2f\n",ZLEmonds());
    }
    return 0;
}

文章目录