//解題思路：樸素的Prim算法
#include <stdio.h>
#include <string.h>????//引入memset的頭文件
#define arraysize 51
int maxData = 0x7fffffff;??//定義最大值
int dis[arraysize][arraysize];?//定義鄰接矩陣
bool final[arraysize];???//標識該點是否在最小生成樹中
int d[arraysize];????//定義最小距離
int P,R;
void Prim()
{
?int i,j;
?int min,v;
?int sum = 0;
?memset(final,0,sizeof(final));?//final初始化
?for(i=1;i<P+1;++i)
?{
??d[i] = dis[1][i];???//最小距離初始化
?}
?final[1] = true;
?d[1] = 0;
?for(i=1;i<P;++i)
?{
??min = maxData;
??for(j=1;j<P+1;++j)
??{
???if(!final[j] && d[j]<min && d[j]<maxData)?//此處別忘了判斷小于最大距離
???{
????min = d[j];
????v = j;
???}
??}
??final[v] = true;
??sum += min;
??for(j=1;j<P+1;++j)
??{
???if(!final[j] && d[j]>dis[v][j] && dis[v][j]<maxData)?//此處別忘了判斷小于最大距離
????d[j] = dis[v][j];
??}
?}
?printf("%d\n",sum);
}
int main()
{
?int i,j;
?int start,end,length;
?//freopen("1.txt","r",stdin);
?while(scanf("%d",&P)!=EOF)
?{
??if(P == 0)
???break;
??//臨界矩陣初始化
??for(i=1;i<P+1;++i)
??{
???for(j=1;j<P+1;++j)
???{
????dis[i][j] = maxData;
???}
??}
??scanf("%d",&R);
??for(i=1;i<R+1;++i)
??{
???scanf("%d%d%d",&start,&end,&length);
???//判斷重邊的情況
???if(dis[start][end]>length)
???{
????dis[start][end] = length;?//無向圖
????dis[end][start] = length;
???}
??}
??Prim();
?}
?return 0;
}

轉載于:https://www.cnblogs.com/north_dragon/archive/2010/05/04/1727166.html

總結

以上是生活随笔為你收集整理的POJ 1287题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。