Coder Space

PKU 1287 Networking--- 最小生成树，Prim算法

简单的最小生成树问题。Prim算法求解。
对于多重边，只存储其中最短的一条。

 1#include<iostream>
 2#include<limits>
 3
 4using namespace std;
 5
 6const int maxP = 51;
 7const int INF = numeric_limits<int>::max();
 8
 9int G[maxP][maxP];
10
11int Prim(int n)
12{
13    int lowcost[maxP];             //到当前部分生成树的最小距离值
14    bool flag[maxP];
15
16    flag[1] = true;
17    for(int i=2; i<=n; i++)
18    {
19        lowcost[i] = G[1][i];
20        flag[i] = false;
21    }
22
23    for(int i=1; i<n; i++)
24    {
25        int temp = INF;
26        int v = 1;
27
28        //搜索下一条最短边加入生成树
29        for(int j=2; j<=n; j++)
30        {
31            if((!flag[j]) && (lowcost[j] < temp))
32            {
33                temp = lowcost[j];
34                v = j;
35            }
36        }
37        flag[v] = true;
38
39        //更新操作
40        for(int j=2; j<=n; j++)
41        {
42            if((!flag[j]) && (G[v][j] < lowcost[j]))
43            {
44                lowcost[j] = G[v][j];
45            }
46        }
47    }
48    
49    int sumLen = 0;
50    for(int i=2; i<=n; i++)
51    {
52        sumLen += lowcost[i];
53    }
54    
55    return sumLen;
56}
57
58int main()
59{
60    int P,R;
61    int a,b,len;
62
63    int i,j;
64
65    cin>>P;
66
67    while(P!=0)
68    {
69        cin>>R;
70
71        //初始化
72        for(i=1; i<=P; i++)
73        {
74            for(j=1; j<=P; j++)
75            {
76                G[i][j] = INF;
77            }
78            G[i][i] = 0;
79        }
80
81        for(i=0; i<R; i++)
82        {
83            cin>>a>>b>>len;
84            if( len < G[a][b] )        //多重边保存最短值
85            {
86                G[a][b] = len;
87                G[b][a] = len;
88            }
89        }
90
91        cout<<Prim(P)<<endl;
92
93        cin>>P;
94    }
95    return 0;
96}
97

posted on 2010-05-13 11:31 David Liu 阅读(237) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论