用惯了克鲁斯卡尔,写个prim用了好久,不练不行啊
题目没什么好说的,就是最小生成树。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int graph[105][105];
int dis[105];
int vis[105];
int main()
{
int n;
int i,j,k;
while(cin>>n)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>graph[i][j];
int min=2000000000;
int ans=0;
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
dis[i]=graph[1][i];
vis[1]=1;
dis[1]=0;
int pos=1;
for(k=1;k<n;k++)
{
int mm=min;
for(i=1;i<=n;i++)
{
if(!vis[i] && dis[i]<mm)
{
mm=dis[i];
pos=i;
}
}
ans+=dis[pos];
vis[pos]=1;
for(j=1;j<=n;j++)
{
if(!vis[j] && dis[j]>graph[pos][j])
{
dis[j]=graph[pos][j];
}
}
}
cout<<ans<<endl;
}
return 0;
}