#include <iostream>
#define N 2300
int g[N][N]={0};
using namespace std;
int main()
{ 
	int lowcost[N],closest[N];
	int i,j,k,min;
	int max=0;
	int n;
	int m;
	int v1,v2,dis;
	while(cin>>n>>m){
	
	memset(g,-1,N*N*sizeof(int));
	max=0;
	//scanf("%c",&v1);
	//跟新最小边，生成邻接矩阵
	for(j=1;j<=m;j++){
		cin>>v1>>v2>>dis;
		if(g[v1][v2]==-1||g[v1][v2]>dis||g[v2][v1]>dis){
			g[v1][v2]=dis;
			g[v2][v1]=dis;
		}
	}
	for(i=1;i<=n;i++){
	g[i][i]=0;
	} 
for(i=1;i<=n;i++){
	for(j=1;j<=n;j++){
	//	printf("%d ",g[i][j]);
	}
//	cout << endl;   
}


//prim算法
for(i=2;i<=n;i++)                       //n个顶点,n-1条边
{lowcost[i]=g[1][i];                   //初始化
  closest[i]=1;                            //顶点未加入到最小生成树中
}
lowcost[1]=0;                          //标志顶点1加入U集合
for(i=2;i<=n;i++)                      //形成n-1条边的生成树
{min=10000;
  k=0;
  for(j=2;j<=n;j++)           //寻找满足边的一个顶点在U,另一个顶点在V的最小边
      if((lowcost[j]<min)&&(lowcost[j]!=0)&&(lowcost[j]!=-1))
      {min=lowcost[j];
       k=j;
      }
	  if(max<min)max=min;
  //printf("(%d,%d)%d\t",closest[k],k,min);
  lowcost[k]=0;                          //顶点k加入U
  for(j=2;j<=n;j++)                     //修改由顶点k到其他顶点边的权值
      if(g[k][j]!=-1&&g[k][j]<lowcost[j]||(g[k][j]>0&&lowcost[j]==-1))
      {
		 // cout<<endl;
		//cout<<g[k][j]<<" "<<lowcost[j]<<" "<<k<<endl;
		lowcost[j]=g[k][j];
		closest[j]=k;
      }
     // printf("\n");
}




cout<<max<<endl;

	}	
	return 0;
}

• Re:PRIM算法wrong了一天了 郁闷了。在线求高人指点。 (1634) dakecaoxin 2010-02-07 20:50:18
  • Re:PRIM算法wrong了一天了 郁闷了。在线求高人指点。 (50) dakecaoxin 2010-02-07 20:51:05