> #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;
> }

• 偶搞错了 (0) ecjtubaowp 2007-08-01 10:55:14