#include<iostream>
using namespace std;
int **Matrix;
int sum=0;
int n;

void Prim()
{
	int max,j,index,i;
	int *N;
	N=new int[n];
	int *c;
	c=new int[n];
	bool *b;
	b=new bool [n];	//1 is tree node,0 is not tree node
	b[0]=1;
	for(i=1;i<n;i++)
		b[i]=0;
	for(i=0;i<n;i++)
	{
		if(Matrix[0][i]!=-1)
		{
			N[i]=0;
			c[i]=Matrix[0][i];
		}
		else
			c[i]=-1;
	}
	for(i=0;i<n-1;i++)
	{
		//search the max edge in array c
		max=-1;
		index=0;
		for(j=1;j<n;j++)
		{
			if(max<c[j] && b[j]==0)
			{
				index=j;
				max=c[j];
			}
		}
		if(c[index]==-1)
		{
			sum=-1;
			return;
		}
		b[index]=1;
		sum=sum+max;
		for(j=0;j<n;j++)		//update N and C
		{
			if(Matrix[index][j]!=-1 && b[j]==0)
			{
				if(Matrix[index][j]>c[j])
				{
					N[j]=index;
					c[j]=Matrix[index][j];
				}
			}
		}
	}
}
int main()
{
	int m,x,y,w;
	cin>>n>>m;
	Matrix=new int*[n];
	int i;
	for(i=0;i<n;i++)
		Matrix[i]=new int[n];
	for(x=0;x<n;x++)
	{
		for(y=0;y<n;y++)
			Matrix[x][y]=-1;		// 初始化邻接矩阵
	}
	for(i=0;i<m;i++)		//输入数据		
	{
		cin>>x>>y;
		cin>>Matrix[x-1][y-1];
		Matrix[y-1][x-1]=Matrix[x-1][y-1];
	}
	Prim();
	cout<<sum<<endl;
}

• 注意有重边 (1372) ecjtubaowp 2007-07-06 16:21:12
  • Re:注意有重边 (6) plator 2007-07-07 18:41:14
  • Re:注意有重边 (19) openthedoor 2007-09-13 17:43:24
    • Re:注意有重边 (37) oibeginner 2007-10-14 08:11:46
      • Re:注意有重边 (35) oibeginner 2007-10-14 08:14:45
        • 什么叫做有重边啊？ (57) 00648154 2007-11-29 10:49:55
          • Re:什么叫做有重边啊？ (88) TOTOT 2007-11-29 22:27:41
            • Re:什么叫做有重边啊？ (835) majiaof 2007-12-02 21:08:53
              • Re:什么叫做有重边啊？ (17) majiaof 2007-12-02 22:10:35