加点法,以一个点为起点,查找与它相连的所有边中最小的一条,把端点加入队列,然后再从这个端点往外扩展其他的边
http://codevs.cn/problem/1078/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#define INF 0x3f3f3f3f;
using namespace std;
int a[105][105],d[100000];
int n,ans,minn,mini;
bool b[1000];
void prime()
{
for(int i = 1;i <= n; ++i)
{
d[i] = INF;
b[i] = 0;
}
for(int i = 2;i <= n; ++i)
if(a[1][i]) d[i] = a[1][i];
b[1] = 1;
for(int i = 1;i < n; ++i)
{
minn = INF;
for(int j = 1;j <= n; ++j)
if(!b[j] && d[j] < minn)
{
minn = d[j];
mini = j;
}
b[mini] = 1;
ans += minn;
for(int j = 1;j <= n; ++j)
{
if(!b[j] && a[mini][j] > 0)
d[j] = a[mini][j];
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n; ++i)
for(int j = 1;j <= n; ++j)
scanf("%d",&a[i][j]);
prime();
}