poj 1258 Agri-Net prim模板 prim与dijkstra的区别

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

很裸地求最小生成树的题目。题意就不多说了，最重要的就是记录一下学会了prim算法。

初学prim，给我的第一感觉就是和dijkstra好像啊，感觉两者的区别还是有的：

1：prim是求最小生成树的算法。

　　dijkstra是求最短路的算法。

2：prim中dis保存的是未加入集合的点，加入集合需要的代价，而中的代价是其他变量保存的。

　　dijkstra中dis保存的是从起点到当前点所花费的最小代价。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <iostream>
 7 using namespace std;
 8 
 9 const int INF = 0x3f3f3f3f;
10 const int maxn = 105;
11 //map记录路径，vis记录是否加入集合，dis记录未加入集合的点与集合的最短距离
12 int map[maxn][maxn], vis[maxn], dis[maxn], n;
13 
14 int prim ()
15 {
16     int i, sum;
17     memset(vis, 0, sizeof(vis));//标记所有的点都在集合外
18     sum = 0;//总花费记为0
19     vis[1] = 1;//把1当成起始集合
20     for (i=2; i<=n; i++)//初始化dis
21         dis[i] = map[1][i];
22     for (int j=1; j<n; j++)
23     {//因为已经加入集合了一个点，所以只需循环n-1次
24         int min = INF, index;
25         for (i=1; i<=n; i++)//寻找加入集合的最优点
26             if (!vis[i] && dis[i]<min)
27             {
28                 min = dis[i];
29                 index = i;
30             }
31             sum += min;//把最优点加入集合
32             vis[index] = 1;
33          for (i=1; i<=n; i++)//对未加入集合的点加入到集合所用的花费进行优化
34                 if (!vis[i] && dis[i]>map[index][i])
35                 dis[i] = map[index][i];
36     }
37     return sum;
38 }
39 int main ()
40 {
41     int s;
42     while (scanf ("%d", &n)!= EOF)
43     {
44         for (int i=1; i<=n; i++)
45             for (int j=1; j<=n; j++)
46             {
47                 scanf ("%d", &s);
48                 map[i][j] = s;
49             }
50         printf ("%d\n", prim ());
51     }
52     return 0;
53 }