prim.txt

来自「里面包含vc的经典算法,如动态规划,分治,回溯,贪心算法等」· 文本 代码 · 共 60 行

#include <iostream>
using namespace std ;
const int N = 10 ;
int n ;
int  closest[N]  ;
double c[N][N] ;
double lowcost[N] ;
bool s[N] ;

void Prim()
{
	int i,j,k ;
	s[0] = 1 ;
	for(  i = 1 ; i < n ; i ++)
	{
		lowcost[i] = c[0][i] ;
		closest[i] = 0 ;
		s[i] = false ;
	}
	for(  i = 1 ; i < n ; i ++)
	{
		double min = 99999 ;
		j = 0 ;
		for( k = 1 ; k < n ; k ++)
			if((lowcost[k] < min)&&(!s[k]))
			{
				min = lowcost[k] ;
				j = k ;
			}
		s[j] = true ;
		cout << closest[j]+ 1<< "->" << j + 1 << endl;
		for( k = 1 ; k < n ; k ++)
			if((c[j][k] < lowcost[k])&&(!s[k]))
			{
				lowcost[k] = c[j][k] ;
				closest[k] = j ;
			}
	}
}


int main()
{
	freopen("in.txt" , "r" , stdin ) ;
	cin >> n ;
	for( int i = 0 ; i < n ; i ++)
		for( int j =  0 ; j < n ; j ++)
			cin >> c[i][j] ;
	Prim() ;
	return 1 ;
}

测试数据如下：
6
1000 6 1 5 1000 1000
6 1000 5 1000  3 1000
1 5 1000 5 6 4
5 1000 5 1000 1000 2
1000 3  6 1000 1000 6
1000 1000 4 2 6 1000