Coder Space

PKU 1258 Agri-Net--- 最小生成树，Prim算法

简单的最小生成树问题，Prim算法求解即可。

 1/*
 2简单的最小生成树问题。Prim算法求解。因题目为稠密图，故用邻接矩阵存储。
 3*/
 4
 5#include<iostream>
 6#include<limits>
 7
 8using namespace std;
 9
10const int maxN = 101;
11const int INF = numeric_limits<int>::max();
12
13int Farms[maxN][maxN];
14
15//Prim算法求最小生成树
16int Prim(int n)
17{
18    /*
19    设S为已加入生成树中的点集，V-S为未加入的点集。对于V-S中的任一结点j，closest[j]是j在S中的一个邻接顶点，它与j具有最小的距离,lowest[j]即为此最小距离值。
20    */
21    int lowcost[maxN];
22    int closest[maxN];
23    bool flag[maxN];
24
25    flag[1] = true;
26
27    //初始化
28    for(int i=2; i<=n; i++)
29    {
30        lowcost[i] = Farms[1][i];
31        closest[i] = 1;
32        flag[i] = false;
33    }
34
35    for(int i=1; i<n; i++)
36    {
37        int temp = INF;
38        int v = 1;
39        
40        //搜索下一条最短边加入生成树
41        for(int j=2; j<=n; j++)
42        {
43            if((!flag[j]) && (lowcost[j] < temp))
44            {
45                temp = lowcost[j];
46                v = j;
47            }
48        }
49        flag[v] = true;
50
51        //更新closest[]与lowcost[]数组
52        for(int j=2; j<=n; j++)
53        {
54            if((!flag[j]) && (Farms[v][j] < lowcost[j]))
55            {
56                lowcost[j] = Farms[v][j];
57                closest[j] = v;
58            }
59        }
60    }
61
62    int sumLen = 0;
63    for(int i=2; i<=n; i++)
64    {
65        sumLen += lowcost[i];
66    }
67    return sumLen;
68}
69
70int main()
71{
72    int N;
73
74    while(cin>>N)
75    {
76        for(int i=1; i<=N; i++)
77        {
78            for(int j=1; j<=N; j++)
79            {
80                cin>>Farms[i][j];
81            }
82        }
83
84        cout<<Prim(N)<<endl;
85    }
86    return 0;
87}
88

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


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


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论