飓风三起 2018-02-04 17:39:48
点我顶贴
收藏
删除
#include<cstdio>
#include<cstring>
#include<climits>
using namespace std;
int n,a[105][105],d[105],ans,mi,p;
bool v[105];
void prim()
{
int i,j;
for(i=2;i<=n;i++) d[i]=INT_MAX;
d[1]=0;
for(i=1;i<=n;i++)
{
mi=INT_MAX;
for(j=1;j<=n;j++)
{
if(v[j]==true && d[j]<mi)
{
p=j; mi=d[j];
}
}
ans+=mi;
v[p]=false;
for(j=1;j<=n;j++)
{
if(a[p][j]<d[j]) d[j]=a[p][j];
}
}
}
int main()
{
int i,j;
memset(a,0,sizeof(a));
memset(v,true,sizeof(v));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0) a[i][j]=INT_MAX;
}
}
prim();
printf("%d",ans);
return 0;
}