2377.txt

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

#include <stdio.h>
#include <vector>
using namespace std;

vector<pair<int,int> > e[1000];
int n;

int prim( ) {
	int i, j, k, dis[1000] = { 0 }, ans = 0;
	bool sign[1000] = { false };

	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( i && dis[k] == 0 )
			return -1;

		sign[k] = true;
		ans += dis[k];
		for( j=0; j<e[k].size(); j++ )
			if( dis[e[k][j].first] < e[k][j].second )
				dis[e[k][j].first] = e[k][j].second;
	}
	return ans;
}

void input( ) {
	int m, a, b, c;
	scanf( "%d%d", &n, &m );
	while( m-- ) {
		scanf( "%d%d%d", &a, &b, &c );
		a--, b--;
		e[a].push_back( make_pair(b,c) );
		e[b].push_back( make_pair(a,c) );
	}
}

int main( ) {
	input( );
	printf( "%d\n", prim( ) );
	return 0;
}