最近在学图方面的知识，拿来练手，结果花了一天的时间才AC，~~~汗
看来对prim算法不熟练啊，以后得多多练习，这个题需要注意几点，首先没有连通的路线要初始化为很大的值，这个题数据比较小，采取邻接矩阵的存储。刚开始为了二维数组的传递耗了半天，，基础知识不熟。。上代码吧。
prim算法描述：
TE为解的顶点集合,U为生成树的边的集合。
第一步：初始化边的集合，有连通的则初始化为其权值，否则存储计算机内允许的最大值.
第二步;选定起点开始逐步寻找，由于是最小生成树，所以令任意一点为起始点都是可行的，假设选择第一个，则找出其他点与该点之间权值，将其放入解的集合中，这一步骤在算法中应执行多次，每执行一次，集合TE和U都将发生变化，分别增加一条边和一个顶点，因此，TE和U是两个动态的集合，这一点在理解算法时要密切注意。
第三步:当边为n-1条时算法结束。
评价（百科)
此算法的精妙之处在于对求权值最小的边这一问题的分解（也正是由于这种分解，而导致了算法理解上的困难）。按照常规的思路，这一问题应该这样解决：分别从集合V－U和U中取一顶点，从邻接矩阵中找到这两个顶点行成的边的权值，设V－U中有m个顶点，U中有n个顶点，则需要找到m*n个权值，在这m*n个权值中，再查找权最小的边。循环每执行一次，这一过程都应重复一次，相对来说计算量比较大。而本算法则利用了变量tree中第k+1到第n－1号元素来存放到上一循环为止的一些比较结果，如以第k+1号元素为例，其存放的是集合U中某一顶点到顶点tree.en的边，这条边是到该点的所有边中权值最小的边，所以，求权最小的边这一问题，通过比较第k+1号到第n－1号元素的权的大小就可以解决，每次循环只用比较n－k－2次即可，从而大大减小了计算量。
#include<iostream>
using namespace std;
#define Max 1000
int dis[505][505];
int prim(int);
int main()
{
int test;
cin>>test;
while(test--)
{
int i,j,num,edge,x,y,z,sum=0,min=Max;
cin>>num>>edge;
for(i=0;i<=num;++i) //初始化
for(j=0;j<=num;++j) dis[i][j]=Max; //类似无穷大
for(i=0;i<edge;++i)
{
cin>>x>>y>>z;
dis[x][y]=dis[y][x]=z;
}
sum=prim(num);
for(j=0;j<num;++j)
{
cin>>x;
if(x<min) min=x;
}
cout<<sum+min<<endl;
}
system("pause");
return 0;
}
int prim(int n)
{
int lower[n+1];
bool visited[n+1];
int i,j,k,q,sum=0;
for(i=1;i<=n;++i) //假设从顶点1开始
{
lower[i]=dis[1][i]; //与1顶点相关的边
visited[i]=false;
}
visited[1]=true; //标记已在集合中
for(j=1;j<n;++j) //找出n-1条边，故n-1次循环
{
int min=Max;
for(k=1;k<=n;++k) //循环比较找出相邻最小边
{
if(lower[k]<min&&(!visited[k]))
{
min=lower[k];
q=k;
}
}
sum=sum+min;
visited[q]=true; //放入集合
for(k=1;k<=n;++k) //更新集合中的点与未在集合中的顶点之间相关边的权值
if(dis[q][k]<lower[k]&&(!visited[k])) //利用上层循环，比较选择是否更新到某点的最小权值
lower[k]=dis[q][k]; //放入lower数组
}
return sum;
}