> #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了一天了 郁闷了。在线求高人指点。 (50) dakecaoxin 2010-02-07 20:51:05