> #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:终于AC了……了解了重边判断啦！！ (0) zsc08_wangqiang 2010-02-20 12:09:41
  • Re:发现了一个问题，不用判断重边也能AC……？？？？无解？ (0) zsc08_wangqiang 2010-02-20 12:18:37