#include<iostream> 
using namespace std;

const int N = 1002;

int W[N][N],Distance[N];
int nearest[N],n,T = 0;

bool s[N],flag=true;

void prim(void)
{ 
	int i,j,k;
	int max=-1000000000;
	s[1]=true;
	for(i=2;i<=n;i++)
	{ 
		Distance[i]=W[1][i];
		nearest[i]=1;
		s[i]=false;
	} 
	for(i=1;i<n;i++)
	{
		max=-1000000000;
		j=1;
		for(k=2;k<=n;k++)
		if(!s[k]&&Distance[k]>max)
		{ 
			max=Distance[k];
			j=k;
		} 
		T+=W[j][nearest[j]];
		if(nearest[j]<1)
		{ 
			flag=false;
			return;
		} 
		s[j]=true;
		for(k=2;k<=n;k++)
			if(!s[k]&&W[k][j]>Distance[k])
			{ 
				Distance[k]=W[k][j];
				nearest[k]=j;
			} 
	} 
} 
int main(){ 
	int i,a,b,c,m;
	cin>>n>>m;
	for(a=1;a<=n;a++)
		for(b=1;b<=n;b++)
			W[a][b]=-1000000000;
	for(i=1;i<=m;i++)
	{ 
		cin>>a>>b>>c;
		if(W[a][b]<c)
		W[a][b]=W[b][a]=c;
	} 
	prim();
	if(flag)cout<<T<<endl;else cout<<-1<<endl;
	return 0;
}

• Re:prim (1057) leila_n 2008-12-22 13:24:18
• Re:prim (1057) leila_n 2008-12-22 16:12:57