#include <iostream>
#include <stdio.h>
#include <memory>
using namespace std;

int vec,no;  //vec:顶点个数
int adj[101][101],lowcost[101],chosen[101];//lowcost[i] 为从i到u的最小距离，closest[i]=0表示i在u集合中，

bool closest[101];

void Prim()
{
	int i,j,temp;
	for ( i=1;i<=vec;i++)
	{
		temp=INT_MAX;
		if(closest[i]){
			for(j=0;j<no;j++)
				if(adj[i][ chosen[j] ]<temp)
					temp=adj[i][ chosen[j] ];
			lowcost[i]=temp;
		}
	}		
	
	int min,k,sum=0;
	for (i=1 ; i<=vec-no; i++)
	{
		min=INT_MAX;
		for ( j=1;j<=vec;j++)
		{
			if (closest[j]&&lowcost[j]>0&&lowcost[j]<min)
			{
				min=lowcost[j];
				k=j;
			}
		}
		sum+=lowcost[k];
		closest[k]=0;
		for (j=1;j<=vec;j++)
		{
			if (closest[j]&&adj[k][j]>0&&(lowcost[j]<0||adj[k][j]<lowcost[j]))
			{
				lowcost[j]=adj[k][j];
			}
		}//end for
	}//end for
	printf("%d\n",sum);
}

int main()
{
	cin>>vec;
	for (int i=1;i<=vec;i++)
		for(int j=1;j<=vec;j++)
		{
			scanf("%d",&adj[i][j]);
			if(adj[i][j]==0) adj[i][j]=-1; //
		}
	int q,a,b;
	scanf("%d",&q);
	memset(closest,1,sizeof(closest));
	while(q--)
	{
		scanf("%d%d",&a,&b);
		if(closest[a]) chosen[no++]=a;
		if(closest[b]) chosen[no++]=b;
		closest[a]=closest[b]=0;
	}
	if(no==0)
	{
		chosen[no++]=1;
		closest[1]=0;
	}
	Prim();//
	return 0;
}

• Re:这样的程序为什么会是WA，小牛们进来看一下啊？被阴了！！ (72) nofree 2007-11-22 19:52:34
  • Re:这样的程序为什么会是WA，小牛们进来看一下啊？被阴了！！ (92) bigrabbit 2011-03-25 19:45:10