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

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

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

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

　　dijkstra是求最短路的算法。

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

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

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 const int INF = 0x3f3f3f3f;

 const int maxn = ;

 //map记录路径，vis记录是否加入集合，dis记录未加入集合的点与集合的最短距离

 int map[maxn][maxn], vis[maxn], dis[maxn], n;

 int prim ()

 {

     int i, sum;

     memset(vis, , sizeof(vis));//标记所有的点都在集合外

     sum = ;//总花费记为0

     vis[] = ;//把1当成起始集合

     for (i=; i<=n; i++)//初始化dis

         dis[i] = map[][i];

     for (int j=; j<n; j++)

     {//因为已经加入集合了一个点，所以只需循环n-1次

         int min = INF, index;

         for (i=; i<=n; i++)//寻找加入集合的最优点

             if (!vis[i] && dis[i]<min)

             {

                 min = dis[i];

                 index = i;

             }

             sum += min;//把最优点加入集合

             vis[index] = ;

          for (i=; i<=n; i++)//对未加入集合的点加入到集合所用的花费进行优化

                 if (!vis[i] && dis[i]>map[index][i])

                 dis[i] = map[index][i];

     }

     return sum;

 }

 int main ()

 {

     int s;

     while (scanf ("%d", &n)!= EOF)

     {

         for (int i=; i<=n; i++)

             for (int j=; j<=n; j++)

             {

                 scanf ("%d", &s);

                 map[i][j] = s;

             }

         printf ("%d\n", prim ());

     }

     return ;

 }