poj1258Agri-Net 最小生成树prim
浏览数：29 /
时间：2015年06月09日
看了一上午才看懂~~渣渣学习中
#include <stdio.h>
#include <string.h>
#define inf 0x3fffffff
int visit[101],map[101][101],minpos[101],n;
int prim()
{
int pos,t=0,ant=0,p,min;
visit[0]=1;
minpos[t++]=0;
while(t<n)
{
min=inf;
for(int i=0;i<t;i++)
{
p=minpos[i];
for(int j=0;j<n;j++)
{
if(min>map[p][j]&&!visit[j])
min=map[p][j],pos=j;
}
}
ant+=min;
minpos[t++]=pos;
visit[pos]=1;
}
return ant;
}
int main()
{
int x;
while(scanf("%d",&n)!=EOF)
{
memset(visit,0,sizeof(visit));
memset(map,inf,sizeof(map));//map初始为最大值
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&x);
map[i][j]=map[j][i]=x;
}
printf("%d\n",prim());
}
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
