题目链接：http://poj.org/problem?id=1287
题目描述：
请先参考关于prim算法求最小生成树的讲解博客：https://www.cnblogs.com/LJHAHA/p/10051069.html
代码实现：
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 100
#define MAXCOST 0x7fffffff int graph[MAX][MAX]; int prim(int graph[][MAX], int n)
{
int lowcost[MAX];//lowcost[i]:表示以i为终点的边的最小权值,注意i的起点并不确定
int mst[MAX];//mst[i]:表示对应lowcost[i]的起点
int i, j, min, minid, sum = ;
//我们设V1是起点，进行初始化
for (i = ; i <= n; i++)
{
lowcost[i] = graph[][i];//如果该顶点未与V1相连，lowcost值为MAXCOST
mst[i] = ;//刚开始的时候，对于每一个Vi来说，它的起点都是V1
}
mst[] = ;//当mst[i]=0表示起点i加入MST
for (i = ; i <= n; i++)//执行n-1次，保证V1到达每个顶点的最短边都能够找到
{
min = MAXCOST;
minid = ;//起点Vi到顶点minid的边最短
for (j = ; j <= n; j++)//找出最短的边，用minid记录下该顶点，用min存下最短边
{
if (lowcost[j] < min && lowcost[j] != )
{
min = lowcost[j];
minid = j;
}
}
sum += min;//每找出一条最短边就加到权值中去
lowcost[minid] = ;//当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
for (j = ; j <= n; j++)
{
if (graph[minid][j] < lowcost[j])
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
return sum;
} int main()
{
int i, j, k, m, n;
int x, y, cost;
while(scanf("%d%d",&m,&n)){
if(m==)
break;
//初始化图G
for (i = ; i <= m; i++)
{
for (j = ; j <= m; j++)
{
graph[i][j] = MAXCOST;
}
}
//构建图G
for (k = ; k <= n; k++)
{
cin >> i >> j >> cost;
if(cost<graph[i][j]){
graph[i][j] = cost;
graph[j][i] = cost;
}
}
//求解最小生成树
cost = prim(graph, m);
//输出最小权值和
cout <<cost << endl;
}
return ;
}