E - Agri-Net (最小生成树) -- prim算法

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

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=193#problem/E

prim算法思想和步骤总结（自己所写）

dis【】，map【】【】，vis【】，pos ，min，ans（主要定义的变量）

首先，prim算法用于计算图边径长度已知的图，它所求的是将图中所有顶点相连接，所需要的最短路径的长度，prim算法适合计算稠密图，它的主要思想是贪心思想，贪心准则为每次选择未加入树中且距离树最小的顶点，并用dis【】数组不断更新各个顶点到树的距离，由于顶点数有N个，所以要加入N次，初始化一个顶点，先将一个顶点加入树中，剩余的将进入n-1次循环逐步加入树中。再加入树中后，需要进行松弛操作，更新dis【】数组，使dis【】数组中的数值始终是未加入树中的顶点到生成的树的最短距离。

具体步骤以及需要注意点

1.在未加入边之前先将图初始化，将图中点与点之间的距离初始化为无穷，点本身的距离为0.

2. 根据题目要求输入边的长度，不要忘记判断现有长度和新加入的边的长度进行比较，只有新加入边的长度小于现有边的长度才更新它

3.先随机选择一个点加入树中，（判断点是否加入树中，需要借助vis【】，数组，若vis【1】 = 1，表明 1号节点已加入树中）

4.下一步将进行n-1次循环，选择n-1个点加入树中，每次通过 j循环遍历所有的点判断距离，找出最短距离，加入树中。

5.将最短距离加入 ans上 ans += min；

6.进行松弛操作，也需要遍历所有的点，只有该节点未被访问并且该节点到新加入的节点 pos 的距离小于到树的距离，则更新之。

if(!vis[j] && dis[j]>map[pos][j])
dis[j] = map[pos][j];

#include <stdio.h>
#include <string.h>
#define INF 1<<20

int map[101][101];
int dis[101];
int vis[101];

long long ans;
void prim(int n)
{
    int i,j;
    memset(dis,INF,sizeof(dis));
    vis[1] = 1;
    dis[1] = 0;
    for(i = 1;i<=n;i++)
    {
        dis[i] = map[1][i];
    }
    int min,pos;
    for(i = 1;i<=n-1;i++)
    {
       min = INF;
       for(j = 1;j<=n;j++)
       {
           if(!vis[j] && dis[j]<min)
           {
               min = dis[j];
               pos = j;
           }
       }
       vis[pos] = 1;
       ans += min;
       for(j = 1;j<=n;j++)
       {
           if(!vis[j] && dis[j]>map[pos][j])
           dis[j] = map[pos][j];
       }
    }
}
int main()
{
    int n;
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        for(i = 1;i<=n;i++)
        {
            for(j = 1;j<=n;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        prim(n);
        printf("%lld\n",ans);
        ans = 0;
    }
    return 0;
}