#include <stdio.h>
int vexnum,roadnum;
int adj[100][100],mincost[100],res=0;
bool linked[100];

void createCraph()
{
	scanf("%d",&vexnum);
	for(int i=0;i<vexnum;i++)
	{
		mincost[i]=1005;
		for(int j=0;j<vexnum;j++)
			scanf("%d",&adj[i][j]);
	}
	scanf("%d",&roadnum);
	int a,b,temp=roadnum;
	while(temp--)
	{
		scanf("%d%d",&a,&b);
		linked[a-1]=linked[b-1]=1;
	}
	if(roadnum)
	{
		for(int k=0;k<vexnum;k++)
			for(int j=0;j<vexnum;j++)
				if(!linked[k]&&linked[j]&&adj[k][j]<mincost[k])
					mincost[k]=adj[k][j];
	}
}

void prim()
{
	int min,id=-1,i,j,k;
	for(i=1;i<vexnum-roadnum;i++)
	{
		min=1005;
		for(j=0;j<vexnum;j++)
			if(mincost[j]<min)
			{
				min=mincost[j];
				id=j;
			}
		if(id>=0)
		{
			res+=min;
			linked[id]=1;
			mincost[id]=1005;
			for(j=0;j<vexnum;j++)
				if(!linked[j]&&adj[j][id]<mincost[j])
					mincost[j]=adj[j][id];
		}
		else
		{
			int id1,id2;
			for(j=0;j<vexnum;j++)
				for(k=0;k<vexnum;k++)
					if(j!=k&&adj[j][k]<min)
					{
						min=adj[j][k];
						id1=j;
						id2=k;
					}
			linked[id1]=linked[id2]=1;
			mincost[id1]=mincost[id2]=1005;
			res+=min;
			for(k=0;k<vexnum;k++)
				for(j=0;j<vexnum;j++)
					if(!linked[k]&&linked[j]&&adj[k][j]<mincost[k])
						mincost[k]=adj[k][j];
		}
	}
}
int main(int argc, char* argv[])
{
	createCraph();
	prim();
	printf("%d\n",res);
	return 0;
}

• 有重边 (1575) ecjtubaowp 2007-08-01 10:54:03
  • 偶搞错了 (0) ecjtubaowp 2007-08-01 10:55:14