hiho#1097最小生成树一·Prim算法

题目链接:https://hihocoder.com/problemset/problem/1097

从单一顶点开始,Prim 算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
输入:一个加权连通图,其中顶点集合为V,边集合为E;
初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {};
重复下列操作,直到Vnew = V:
在集合E中选取权值最小的边(u, v),其中u为集合Vnew中的元素,而v则是V中没有加入Vnew的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
将v加入集合Vnew中,将(u, v)加入集合Enew中;
输出:使用集合Vnew和Enew来描述所得到的最小生成树。

——Wikipedia

注:Prim和dijkstra算法好像啊。

#include <iostream>
#include <cstdio>
#include <cstring>

const int MAX = 1000;
int A[MAX][MAX];
bool visit[MAX];
int main() {
int n,result=0;
memset(A,1,sizeof(A));
memset(visit,0,sizeof(visit));
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&A[i][j]);
//Prim
visit[1]= true;
for(int t=1;t<n;t++)
{
int k=0;
for(int i=1;i<=n;i++)
{
if(!visit[i] && A[1][i]<A[1][k])
k = i;
}

result += A[1][k];

visit[k]= true;

A[1][k]=A[k][1]=0;

for(int i=1;i<=n;i++)
{
if(!visit[i]&&A[1][i]>=(A[1][k]+A[k][i]))
{
A[1][i]=A[i][1] = A[1][k]+A[k][i];
}
}
}
printf("%d",result);

return 0;
}
文章作者: myth
文章链接: http://meng.li/2017/06/20/prim/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 梦里