POJ 1258 Agri-Net（最小生成树 Prim 模版题）

浏览数：19 / 时间：2015年06月09日

大意：新镇长竞选宣言就是将网络带到每一个农场，给出农场个数，两两之间建光缆的耗费，求所有都联通的最小耗费。

思路：最小生成树，因为边比较稠密，用Prim做。

PS；对于比较稠密的图，用Prim，对于比较稀疏的图，用 Kruskal。Kruskal是找边的过程，稀疏的话会比较快。

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