POJ 2485 Highways（最小生成树 Prim）

大意：给你一个用邻接矩阵形式存储的有n个顶点的无向图，让你求它的最小生成树并求出在这个生成树里面最大的边的权值。

思路：用Prim求，判断条件改一下就行。

PS：dis数组初始化的时候用memset一直RE，希望有知道怎么回事的不吝赐教，谢了~

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define INF 0x3f3f3f3f
 4 
 5 int Map[510][510];
 6 int dis[510];
 7 int n, m;
 8 
 9 int min(int a, int b)
10 {
11     return a > b ? b : a;
12 }
13 
14 int Prim()
15 {
16     int Min_ele, Min_node;
17     for(int i = 1; i <= n; i++)
18     {
19         dis[i] = INF;
20     }
21     ///这里如果用memset(dis, INF, sizeof(dis));的话会一直RE
22     int r = 1;
23     int Ans = 0;
24     for(int i = 1; i < n; i++)
25     {
26         Min_ele = INF;
27         dis[r] = -1;
28         for(int j = 1; j <= n; j++)
29         {
30             if(j != r && dis[j] >= 0)
31             {
32                 dis[j] = min(dis[j], Map[r][j]);
33                 if(dis[j] < Min_ele)
34                 {
35                     Min_ele = dis[j];
36                     Min_node = j;
37                 }
38             }
39         }
40         r = Min_node;
41         if(Min_ele > Ans)
42             Ans = Min_ele;
43     }
44     return Ans;
45 }
46 
47 void Solve()
48 {
49     scanf("%d", &m);
50     while(m--)
51     {
52         scanf("%d", &n);
53         memset(Map, 0, sizeof(Map));
54         for(int i = 1; i <= n; i++)
55         {
56             for(int j = 1; j <= n; j++)
57             {
58                 scanf("%d", &Map[i][j]);
59             }
60         }
61         printf("%d
", Prim());
62     }
63 }
64 
65 int main()
66 {
67     Solve();
68 
69     return 0;
70 }

Highways