布线问题（普利姆算法）

普里姆（Prim）算法

　　1.基本思想：设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是G的最小生成树， T的初始状态为U={u0}（u0∈V），TE={}，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。即：

（1）从连通网络 G = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。

　　（2）以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。

示例：

昨晚上学长讲了最小生成树中的普利姆算法，不过没有将代码实现，今天纠结了一天，嘿嘿，终于搞明白了一点，这个题是一个赤裸裸的最小生成树问题，也许会有很多错误，希望有人能帮我找出.

题目：布线问题

原题地址：请猛击

AC代码

时间：32ms 内存：1212

#include<stdio.h>
#include<string.h>
int m[502][502],flag[502];
int prim(int n)     //用普利姆算法找最小生成树函数
{
	int i,j,sum=0,min,temp;
	i=1;
	for(int k=1;k<n;k++)
	{
		flag[i]=1;   //i为研究对象   flag为标记该点是否研究过，确定最小分支
		min=999999;
		for(j=1;j<=n;j++)             //更新各个点对应的最小值
		{
			if(m[0][j]==0)
				m[0][j]=m[i][j];       
            else if(!flag[j]&&m[0][j]>m[i][j])
				m[0][j]=m[i][j];
		}
		for(j=2;j<=n;j++)
		{
			if(!flag[j] &&min>m[0][j])               //确定该研究对象中的最小分支
			{
				min=m[0][j];
				temp=j;
			}
		}
		i=temp;
		sum+=min;
	}
	return sum;
}
int main()
{
	int n,i,j,k,l,p,weight;
	scanf("%d",&n);
	while(n--)
	{
		int min=9999999;
		memset(m,0,sizeof(m));
		memset(flag,0,sizeof(flag));
		scanf("%d%d",&k,&l);
		for(p=1;p<=l;p++)
		{
			scanf("%d%d%d",&i,&j,&weight);
			m[i][j]=weight;     //将各个点添加到二维数组中
			m[j][i]=weight;
		}
		for(p=1;p<=k;p++)
		{
			scanf("%d",&weight);          //找出最少费用
			if(min>weight)
				min=weight;
		}
		printf("%d\n",prim(k)+min);
	}
	return 0;
}