#include<iostream>
using namespace std;
int mat[102][102],minv[102];bool v[102];
int main()
{
	int n,q,i,j,x,y,ret,k;
	while(scanf("%d",&n)!=EOF)
	{
     //memset(minv,0xf,sizeof(minv));//无穷大

		for(i=0;i<=n;i++)
			minv[i]=100000000;

     memset(v,false,sizeof(v));

     for(i=1;i<=n;i++)//n条路径输入
	 {
		 for(j=1;j<=n;j++)
		 scanf("%d",&mat[i][j]);
	 }
     
	 scanf("%d",&q);

	 for(i=0;i<q;i++)//已有路径
	 {
		 scanf("%d %d",&x,&y);
		 mat[x][y]=0;//赋值为0
	 }

	 for(minv[i=1]=0,ret=0;i<=n;i++)
	 {
      for(k=-1,j=1;j<=n;j++)
		  if(!v[j]&&(k==-1||minv[j]<minv[k]))
			  k=j;
          
	 for(j=1,ret+=minv[k],v[k]=true;j<=n;j++)
	 {
		 if(!v[j]&&mat[k][j]<minv[j])
			 minv[j]=mat[k][j];
	 }


	 }

	 printf("%d\n",ret);
	}
	return 0;
}

• Re:我用prim算法怎么过不了，高手给看下吧 (122) ding59 2009-02-21 14:02:56