1258.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

const int size = 1000;
typedef int type;
type e[size][size];


////////////////////////////////////////////////////////////////
//prim
//
//O(n^n)
//
//e为边权矩阵( < 0 表示边不存在 )，n为节点个数
//
//f返回每个节点在最小生成树中的父亲,( 标号为0的节点为根 ) ,v返回权值之和
//
//函数返回图连通否

bool prim( int n, type e[size][size], int f[size], type &v )
{
	int i, j, k;
	type total = 0;
	vector<bool> sign(size,0);
	vector<type> value(size,-1);

	value[0] = 0;
	if( f ) f[0] = -1;

	for( i=0; i<n; i++ )
	{
		k = -1;
		for( j=0; j<n; j++ )
			if( !sign[j] && value[j]>=0 && ( k<0 || value[j]<value[k] ) )
				k = j;

		if( k < 0 ) return false;

		sign[k] = true;
		total += value[k];

		for( j=0; j<n; j++)
			if( e[k][j] >=0 && !sign[j] && ( value[j]<0 || e[k][j] < value[j] ) )
			{
				value[j] = e[k][j];
				if( f ) f[j] = k;
			}
	}

	v = total;

	return true;
}

///////////////////////////////////////////////////////////////////

int main()
{
	int n, i, j, s;
	while( scanf( "%d", &n ) == 1)
	{
		for( i=0; i<n; i++ )
		for( j=0; j<n; j++ )
			scanf( "%d", &e[i][j] );

		prim( n, e, 0, s );
	
		printf( "%d\n", s );
	}

	return 0;
}