下面是我的程序，用prim做的。
重边也考虑到了啊，为什么会wa？

#include<iostream>
using namespace std;

int main()
{
	int i,j,k;
	int n,m;
	int temp,totalcost=0,count=1;
	int cost[101][101];
	bool mark[1010];
	cin>>n>>m;
	int *MST=new int [n];
	memset(cost,0,sizeof(cost));
	memset(mark,0,sizeof(mark));
	for(i=0;i<m;i++)
	{
		cin>>j>>k>>temp;
		if(temp<cost[j][k]) continue;
		cost[k][j]=cost[j][k]=temp;
	}
	MST[0]=1;
	mark[1]=1;
	int max=0,flag;
	while(count<n)
	{
		max=0;
		i=MST[count-1];
		for(j=1;j<=n;j++)
			if(cost[i][j]>0 && mark[j]==0)
			{
				if(cost[i][j]>max)
				{
					max=cost[i][j];
					flag=j;
				}
			}
		if(max==0)
		{
			cout<<-1<<endl;
			return 0;
		}
		mark[flag]=1;
		MST[count]=flag;
		totalcost+=cost[i][flag];
		count++;
	}
	cout<<totalcost<<endl;
	delete MST;
	return 0;
}

• Re:什么叫做有重边啊？ (17) majiaof 2007-12-02 22:10:35