2421.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
int e[110][110],n;
int sign[110];
int ans;
int d[110];

void init()
{
	int i,j,m;
	cin>>n;

	for(i=0;i<n;i++)
	for(j=0;j<n;j++)
		cin>>e[i][j];
    cin>>m;
	
	while(m--)
	{
		cin>>i>>j;
		e[i-1][j-1]=0;
		e[j-1][i-1]=0;
	}
}

void prim()
{
	int i,j,k;
	for(i=0;i<n;i++)
	{
		sign[i]=1;
		d[i]=99999;
	}
	ans=0;

	d[0]=0;
	for(i=0;i<n;i++)
	{
		k=-1;
		for(j=0;j<n;j++)
		if(sign[j]&&(k<0||d[k]>d[j]))
			k=j;
		
		ans+=d[k];
		sign[k]=0;
		
		for(j=0;j<n;j++)
			if(sign[j]&&d[j]>e[k][j])
				d[j]=e[k][j];
	}

}

int main()
{
	init();
	prim();
	cout<<ans<<endl;
	return 0;
}