事情是这样的，poj上有个1789，是一个mst的题。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1789
开始用kruscal做直接就tle了，用prim做才过了。时间限制是2000MS，prim用了900多。prim确
实要比kruscal快些，是用最弱智的方法维护最小优先序列就这样，如果使用斐波纳契堆的话效果可想而知了，可惜我现在还不会用斐波纳契堆，加油加油
啊。感觉kruscal主要慢在排序那儿，确实很慢，尤其是大数据量的时候。
这两天也写了些mst的题，感觉没有什么大的问题了。上一篇日志总结了一下kruscal，现在总结一下prim。
需要三个数组：map[][]，key[]，pi[]，int型的，分别记录两点的距离、当前状态下的key值和父节点。需要一个bool型的q[]来判断当前点是否在集合Q里头。
一个getm()函数来取得当前集合里头最小key的那个节点，如下：
int getm()
{
int re,m=0x7fffffff,t;
for(t=0;t<cas;t++)
{
if(q[t] && key[t]<m)
{
m=key[t];
re=t;
}
}
q[re]=false; //千万别忘了把弹出的值去掉标记，不然下次又是它了。
return re;
}
prim()的函数如下：
int prim()
{
memset(q,true,sizeof(q));
memset(key,0x7f,sizeof(key));
memset(pi,-1,sizeof(pi)); //所有节点的父节点初始化诶NIL
key[0]=0;
int u,t,tt,n=N,re=-1; //re根据需要初始化，最长路径，最短路径，总路径等等。
while(n--) //n--确保遍历到所有的顶点。
{
u=getm();
for(t=0;t<N;t++)
{
if(q[t] && map[t][u]<key[t])
{
key[t]=map[t][u];
pi[t]=u;
}
}
}
for(t=0;t<N;t++)
{
if(pi[t]==-1) continue; //除去根节点
if(re<map[t][pi[t]])
re=map[t][pi[t]]; //根据需求写代码～求最大路径、最小路径、总路等。
}
return re;
}
最后说下最近：
赶紧把各点之间的最短路看一下，同时练习最短路，dijsktra和bellman-ford，尤其是bellman那个算法还不是很理解，赶紧问问。
好吧～