1679.txt

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

#include <stdio.h>
#include <memory.h>

int dis[101];
int count[101];

bool sign[101];
int e[100][100], n;

int prim( ) {
	int i, j, k, ans = 0;
	memset( sign, 0, sizeof sign );
	memset( dis, 0x0f, sizeof dis );
	memset( count, 0, sizeof count );
	
	dis[0] = 0;
	for( i=0; i<n; i++ ) {
		k = -1;
		for( j=0; j<n; j++ )
			if( !sign[j] && ( k < 0 || dis[j]<dis[k] ) )
				k = j;
		
		if( count[k] > 1 )
			return -1;

		sign[k] = true;
		ans += dis[k];

		for( j=0; j<n; j++ )
			if( !sign[j] ) {
				if( e[k][j] == dis[j] )
					count[j]++;
				else if( e[k][j] < dis[j] )
					dis[j] = e[k][j], count[j] = 1;
			}
	}

	return ans;
}

int main( ){
	int t, i, j, w, m;
	scanf( "%d", &t );
	while( t-- ) {
		scanf( "%d%d", &n, &m );
		memset( e, 0x0f, sizeof e );

		while( m-- ) {
			scanf( "%d%d%d", &i, &j, &w );
			e[i-1][j-1] = e[j-1][i-1] = w;
		}

		w = prim( );
		if( w < 0 )
			printf( "Not Unique!\n" );
		else
			printf( "%d\n", w );
	}

	return 0;
}