2075.txt

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

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

using namespace std;

const int size = 1000;
typedef double 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], double &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;
}

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

char name[size][30];

int main()
{
	double l,v;
	int i,j,n,m;
	char name1[100], name2[100];

	scanf( "%lf", &l );
	scanf( "%d", &n );

	for(i=0;i<n;i++)
		scanf( "%s", name[i] );

	scanf( "%d", &m );

	for( i=0; i<n; i++ )
	for( j=0; j<n; j++ )
		e[i][j] = -1;
	
	while( m-- )
	{
		scanf( "%s%s", name1, name2 );
		
		for(i=0;i<n;i++)
			if( strcmp(name1,name[i]) == 0 )
				break;

		for(j=0;j<n;j++)
			if( strcmp(name2,name[j]) == 0 )
				break;

			scanf( "%lf", &e[i][j] );
			e[j][i] = e[i][j];
	}

	prim( n, e, 0, v );

	if( v <= l ) printf( "Need %.1lf miles of cable\n", v );
	else printf( "Not enough cable\n");

	return 0;
}