Coder Space

PKU 2485 Highways--- 最小生成树，Prim算法

最小生成树，求树中的最大边。Prim算法，最后输出lowcost[]表中是大值即可。

 1#include<iostream>
 2
 3using namespace std;
 4
 5const int maxN = 501;
 6const int INF = 65537;
 7
 8int G[maxN][maxN];
 9
10//Prim算法
11int Prim(int n)
12{
13    int lowcost[maxN];           //到当前部分生成树的最小距离值
14    bool flag[maxN];
15
16    flag[1] = true;
17
18    for(int i=2; i<=n; i++)
19    {
20        lowcost[i] = G[1][i];
21        flag[i] = false;
22    }
23
24    for(int i=1; i<n; i++)
25    {
26        int temp = INF;
27        int v = 1;
28
29        //搜索下一条最短边加入生成树
30        for(int j=2; j<=n; j++)
31        {
32            if((!flag[j]) && (lowcost[j] < temp))
33            {
34                temp = lowcost[j];
35                v = j;
36            }
37        }
38        flag[v] = true;
39
40        //更新操作
41        for(int j=2; j<=n; j++)
42        {
43            if((!flag[j]) && (G[v][j] < lowcost[j]))
44            {
45                lowcost[j] = G[v][j];
46            }
47        }
48    }
49
50    //搜索最小生成树中的最大边
51    int longest = 0;
52    for(int i=2; i<=n; i++)
53    {
54        if(lowcost[i] > longest)
55        {
56            longest = lowcost[i];
57        }
58    }
59    return longest;
60}
61
62int main()
63{
64    int T,N;
65
66    int i,j;
67
68    scanf("%d",&T);
69    while(T--)
70    {
71        scanf("%d",&N);
72
73        for(i=1; i<=N; i++)
74        {
75            for(j=1; j<=N; j++)
76            {
77                scanf("%d",&G[i][j]);
78            }
79        }
80
81        printf("%d\n",Prim(N));
82    }
83    return 0;
84}

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


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


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论