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 = 105;
//map记录路径，vis记录是否加入集合，dis记录未加入集合的点与集合的最短距离
int map[maxn][maxn], vis[maxn], dis[maxn], n;

int prim ()
{
    int i, sum;
    memset(vis, 0, sizeof(vis));//标记所有的点都在集合外
    sum = 0;//总花费记为0
    vis[1] = 1;//把1当成起始集合
    for (i=2; i<=n; i++)//初始化dis
        dis[i] = map[1][i];
    for (int j=1; j<n; j++)
    {//因为已经加入集合了一个点，所以只需循环n-1次
        int min = INF, index;
        for (i=1; i<=n; i++)//寻找加入集合的最优点
            if (!vis[i] && dis[i]<min)
            {
                min = dis[i];
                index = i;
            }
            sum += min;//把最优点加入集合
            vis[index] = 1;
         for (i=1; 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=1; i<=n; i++)
            for (int j=1; j<=n; j++)
            {
                scanf ("%d", &s);
                map[i][j] = s;
            }
        printf ("%d
", prim ());
    }
    return 0;
}