#include<iostream>
using namespace std;
#define M 1001

int map[M][M];
int temp[M];
int num[M];
int visit[M];
int n,m,i,j;
int flag = 1;

int prim()
{
	int maxsum=0;
	int maxl;
	temp[0] = -9999999;
	for(i=2; i<=n; i++)
	{
		temp[i] = map[1][i];
		num[i] = 1;
	}
	visit[1] = 1;
	for(i=1; i<n; i++)
	{
		maxl = 0;
		for(j=2; j<=n; j++)	//找最大边
		{
			if( !visit[j] && temp[j] > temp[maxl])
				maxl = j;
		}
		if(num[maxl] < 1)	//判断连通性，好像不对吧？？
		{
			flag = 0;
			break;
		}
		visit[maxl] = 1;
		maxsum += temp[maxl];
		for(j=2; j<=n; j++)
		{
			if( !visit[j] && map[maxl][j] > temp[j])
			{
				temp[j] = map[maxl][j];
				num[maxl] = j;
			}
		}
	}
	return maxsum;
}

int main()
{
	int a,b,c;
	int sum;
	scanf("%d%d",&n,&m);
	
		memset(visit,0,sizeof(visit));
		memset(temp,0,sizeof(temp));
		for(i=1; i<=n; i++)
			for(j=1; j<=n; j++)
				map[i][j] = -100000;
		for(i=1; i<=m; i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			if(map[a][b] < c)
				map[a][b] = map[b][a] = c;
		}
		sum = prim();
		if(flag)
			printf("%d\n",sum);
		else
			printf("-1\n");
	
	return 0;
}

• Re:不知咋滴一直WA…无限次！！！麻烦看下哈……怎么判断连通性？？？？ (1285) zsc08_wangqiang 2010-02-20 11:20:17
  • Re:终于AC了……了解了重边判断啦！！ (0) zsc08_wangqiang 2010-02-20 12:09:41
    • Re:发现了一个问题，不用判断重边也能AC……？？？？无解？ (0) zsc08_wangqiang 2010-02-20 12:18:37