讨论 / 拜年题解
飓风三起 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;

}

查看更多回复
提交回复