Highways(prim)

此题是求最小生成树里的最大权值。prim算法：
 1 #include<stdio.h>
 2 #include<string.h>
 3 const int maxn=505;
 4 const int INF = 1<<28;
 5 int map[maxn][maxn];
 6 int dis[maxn],vis[maxn];
 7 int n,maxm;
 8 void prim()
 9 {
10     int pos;
11     for (int i = 1; i <= n; i ++)
12     {
13         dis[i] = map[1][i];
14     }
15     vis[1] = 1;
16     for (int i = 1; i <= n-1; i ++)
17     {
18         int min = INF;
19         for (int j = 1; j <= n; j ++)
20         {
21             if (!vis[j] && dis[j] < min)
22             {
23                 min = dis[j];
24                 pos = j;
25             }
26         }
27         if(min > maxm)
28         {
29             maxm = min;
30         }
31         vis[pos] = 1;
32         for (int j = 1; j <= n; j ++)
33         {
34             if (!vis[j] && dis[j] > map[pos][j])
35                 dis[j] = map[pos][j];
36         }
37     }
38 }
39 void init()
40 {
41     maxm = -1;
42     for (int i = 0; i <= n; i ++)
43     {
44         for (int j = 0; j <= n; j ++)
45         {
46             map[i][j] = INF;
47         }
48         map[i][i] = 0;
49         vis[i] = 0;
50     }
51 }
52 int main()
53 {
54     int t;
55     scanf("%d",&t);
56     while(t--)
57     {
58         scanf("%d",&n);
59         init();
60         for (int i = 1; i <= n; i ++)
61         {
62             for (int j = 1; j <= n; j ++)
63             {
64                 scanf("%d",&map[i][j]);
65             }
66         }
67         prim();
68         printf("%d
",maxm);
69     }
70     return 0;
71 }
View Code